Trapping Rain Water — LeetCode 42 | Префиксный максимум | Два указателя | Самый популярный сложны...

Задача «Уловить дождевую воду» (LeetCode 42) — одна из самых часто задаваемых сложных задач на собеседованиях по программированию. Сначала изучите ключевую идею: вода над перекладиной = min(самая высокая левая стена, самая высокая правая стена) − высота, как вычисляются префиксные/суффиксные максимумы и почему важна только более короткая сторона. Затем решите задачу шаг за шагом: описание задачи и примеры, что говорят ограничения, сложность перебора O(n²), префиксные максимумы, принцип двухточечной навигации, полный пробный запуск, код на C++ для обеих версий и связанные задачи. 🔥 Одна из самых часто задаваемых задач на собеседованиях по программированию — часто упоминается в отчетах Amazon, Google, Meta, Microsoft, Goldman Sachs (на основе отчетов о собеседованиях в сообществе). В этом видео: • Формула уровня воды выше одного бара • Префиксные и суффиксные максимумы • Почему более короткая сторона всегда является пределом • LeetCode 42: задача, примеры и ограничения • От времени O(n²) до времени O(n), затем O(1) пространства с двумя указателями • Полный тестовый запуск с двумя указателями и код на C++ для обеих версий ⏱️ Разделы 0:00 Один из самых часто задаваемых вопросов на собеседованиях 0:25 Шаблон: сколько воды находится выше одного бара? 0:53 Шаблон: префиксные максимумы и суффиксные максимумы 1:13 Шаблон: важна только более короткая сторона 1:33 Шаблон: быстрый пробный запуск 2:23 Шаблон: как его распознать 2:38 Шаг 1 · Задача: улавливание дождевой воды (LeetCode 42) 3:08 Шаг 1 · Понимание примеров 3:32 Шаг 1 · Ограничения и что они нам говорят 3:53 Шаг 2 · Подход: перебор 4:16 Шаг 2 · Подход: предварительное вычисление обоих максимумов 4:36 Шаг 2 · Подход: два указателя, пространство O(1) 5:05 Шаг 2 · Подход: план 5:29 Шаг 3 · Решение: пробный запуск 6:13 Шаг 3 · Решение: пробный запуск (продолжение) 6:38 Шаг 3 · Решение: пробный запуск выполнение (завершение) 6:57 Шаг 3 · Код: версия с префиксным максимумом 7:15 Шаг 3 · Код: версия с двумя указателями 7:37 Шаг 3 · Решение: сложность 7:57 Тот же шаблон в других местах 8:21 Резюме 8:48 Ставьте лайки и подписывайтесь 🧩 Практика LeetCode 42 · Улов дождевой воды → https://leetcode.com/problems/trappin... LeetCode 11 · Контейнер с наибольшим количеством воды → https://leetcode.com/problems/contain... LeetCode 238 · Произведение массива, кроме самого себя → https://leetcode.com/problems/product... LeetCode 407 · Улов дождевой воды II → https://leetcode.com/problems/trappin... 💻 Полный код на C++: 📺 Анимированные структуры данных и алгоритмы — на C++. Полный плейлист: [добавить ссылку на плейлист] ⏮️ Предыдущий: Эпизод 50 · Сумма комбинаций ⏭️ Следующий: Эпизод 52 · Гниющие апельсины 👍 Поставьте лайк видео и подпишитесь, чтобы получать больше анимационных материалов по структурам данных и алгоритмам. #TwoPointers #CodingInterview #Cpp