Иногда мне нравится писать собственные редакционные статьи для (алгоритмических) задач, которые я решил. Я пишу это в свой журнал CP (Competitive Programming Log — это просто файл google docs, куда я сбрасываю найденные интересные проблемы и свои мысли). Если вы занимаетесь соревновательным программированием или готовитесь к техническому собеседованию, попробуйте написать собственную редакционную статью для задач, которые вы решили. Записывая свои идеи и мысли, вы закрепляете свои знания и учитесь более эффективно излагать свои идеи.

Итак, в этом посте я расскажу о проблеме 42 LeetCode — Улавливание дождевой воды. Вы можете получить доступ к задаче здесь: https://leetcode.com/problems/trapping-rain-water/

Постановка задачи
Вам дана высота некоторой местности и предложено вычислить количество воды, оставшейся после дождя. Высота задается в виде массива неотрицательных целых чисел. Количество воды рассчитывается в количестве блоков.

В задаче не указан размер данного массива. Таким образом, мы должны стремиться к максимально быстрому решению. Поскольку чтение самого массива занимает около O(n), самое быстрое решение будет ограничено процессом ввода и, следовательно, также будет выполняться за O(n).

Мы знаем, что вода будет задерживаться только в чашеобразных структурах. Итак, нам нужно только найти эти чашеобразные структуры и рассчитать количество воды, которое содержится в каждой чаше, верно? Может быть, мы можем пойти слева направо и посмотреть на высоту каждой точки, если она идет вниз, а затем вверх, это должна быть чаша. После этого мы можем рассчитать высоту воды в каждой чаше, взяв минимальную высоту возвышения двух краев соответствующей чаши. Наконец, мы суммируем всю воду в каждой миске и получаем ответ. Это решение работает за O(n).

Да, это решение работает, если мы рассчитываем количество воды только в простых чашеобразных структурах. Проблема не гарантирует такого состояния, поэтому нам нужно знать более сложную форму. Подумайте, что произойдет, если есть вложенные чаши (внутри чаши несколько чаш)? Или если есть странные формы чаши? Или вложенные чаши странной формы?

Давайте попробуем другой способ. Представьте, что мы идем по местности слева направо. Если местность поднимается вверх, мы знаем, что вода не будет захвачена, поскольку вода будет просто стекать туда, откуда мы пришли (левый край). Если местность идет вниз, мы можем предположить два условия:

  • местность идет вниз навсегда, и вода не будет поймана.
  • местность поднимается в какой-то момент позже, и там будет вода в ловушке.

Откуда мы знаем, что местность поднимается в какой-то момент позже, без фактической проверки высоты нескольких точек впереди (это решение может работать, хотя и работает медленнее со сложностью O (n²))? Да, ты прав. Было бы неплохо, если бы кто-то еще (наш друг) с другой стороны сообщил нам высоту местности, чтобы мы могли сделать вывод, всегда ли она поднимается или опускается. Если наш друг находится на более высокой земле, чем наша текущая позиция, мы можем быть уверены, что ландшафт поднимается позже (в точке, где в данный момент стоит наш друг). Поэтому любая местность с более низкой высотой, чем наша текущая позиция, и находящаяся между нашим другом и нами, определенно будет ловушкой для воды. Количество воды, попавшей в точку, будет разницей между высотой нашего текущего положения и высотой соответствующей точки.

Если наш друг находится на более низком уровне, мы не можем ничего сделать (может быть, между нами большая гора или, может быть, вся местность просто спускается с холма от нашего места к месту нашего друга).

Подождите… Что, если, когда наш друг находится на более низком уровне, вместо того, чтобы мы делали выводы из ее положения, она могла бы делать выводы из нашего положения и вычислять для нас количество воды на другой стороне местности? Бум! Это хорошая идея.

Мы можем использовать два указателя: один указывает на начало (левую сторону) местности, а другой указывает на конец (правую сторону) местности. Левый указатель будет двигаться вправо и вычислять количество захваченной воды по мере движения вправо, а правый указатель будет делать то же самое, двигаясь влево.

Временная сложность: O(n).
Пространственная сложность: O(n).

Первоначально опубликовано на vincentalfred.wordpress.com 27 января 2019 г.
Переиздано на blog.vincentalfred.com.