Улавливание дождевой воды — очень известная задача массивов и динамического программирования. Это сложная задача как для LeetCode, так и для компьютерщики для гиков. Но в конце этого блога вы не будете считать эту проблему сложной. :)
В этом блоге мы рассмотрим проблему, начиная с подхода грубой силы и заканчивая оптимизированным.
Постановка задачи:
Учитывая n
неотрицательных целых чисел, представляющих карту высот, где ширина каждой полосы равна 1
, вычислите, сколько воды она может собрать после дождя.
Пример 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
Пример 2:
Input: height = [4,2,0,3,2,5] Output: 9
Ограничения:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
Решение:
Давайте сначала начнем с подхода грубой силы:
Подход грубой силы:
Рассмотрим блок в сером цвете. Мы видим, что он содержит одну единицу воды.
Максимальная высота любого блока слева от него равна 2. А максимальная высота справа от него равна 3. Таким образом, единица воды, которую он содержит, равна:
min(height[left_max],height[right_max]) - height[current_block]; // Thus unit of water stored in the gray block is: min(2,3)-1; i.e. 2-1 = 1 units.
Точно так же блок белого цвета содержит 2 единицы воды, потому что хранится вода:
min(height[left_max],height[right_max]) - height[current_block]; i.e. min(2,3)-0; i.e. 2-0 = 0 units.
Надеюсь, вы поняли основную идею подхода.
Анализ:
У нас будет цикл для обхода массива и однократного покрытия каждого элемента. По каждому индексу мы найдем левое и правое максимальные значения. Таким образом, у нас будет два вложенных цикла, а временная сложность такого подхода будет O(n²). пространственная сложность будет O(1).
Оптимизация:
Давайте немного оптимизируем брутфорс.
Вместо обхода всего массива снова и снова мы можем поддерживать два разных массива для хранения левого и правого максимальных значений.
При таком подходе мы можем решить вопрос только с одним циклом.
Таким образом, временная сложность этого подхода составляет O(n).
А поскольку мы использовали дополнительное пространство, пространственная сложность также составляет O(n).
Мы уменьшили временную сложность с O(n²) до O(n). Мы, безусловно, заслужили похлопывание по спине. :)
Теперь давайте углубимся и рассмотрим более оптимизированный подход.
Оптимизированный подход:
Мы будем использовать концепцию двух указателей.
Во-первых, объявите левый и правый указатели. Инициализируйте левый указатель на 0, а правый на n-1 (где n — размер массива) в начале. Кроме того, сохраните две переменные left_max и right_max и установите для них значение 0.
int n = height.size(); int left=0,right = n-1; int left_max = 0,right_max = 0; int result = 0;
Сохраните воду в переменной результата.
Теперь, помня об этих переменных, давайте посмотрим на следующие вещи:
- Блок на высоте[слева] будет хранить воду только в том случае, если у него есть блок выше него с обеих сторон. Таким образом, мы должны выполнить два условия для блока на height[left], чтобы хранить немного воды.
height[left]<=height[right] and height[left]<left_max
Таким образом, мы обновим результат на result + height[left]
2. Но, если height[left]≤height[right] и height[left]≥left_max, мы обновим left_max на height[left ].
Затем мы переместим наш левый указатель вперед на одну позицию.
3. Аналогично, если блок на height[right] больше, чем height[left], возможны две ситуации:
if(height[right]>=right_max){ right_max = height[right]; }else{ result += (right_max-height[right]); }
Мы переместим наш правый указатель назад на одну позицию.
Весь код можно записать так:
class Solution { public: int trap(vector<int>& height) { int n = height.size(); int left=0,right = n-1; int left_max = 0,right_max = 0; int result = 0; while(left<=right){ if(height[left]<=height[right]){ if(height[left]>=left_max){ left_max = height[left]; }else{ result+= (left_max-height[left]); } left++; }else{ if(height[right]>=right_max){ right_max = height[right]; }else{ result += (right_max-height[right]); } right--; } } return result; } };
Анализ:
Поскольку мы проходим по массиву только один раз, временная сложность этого подхода равна o(n).
Кроме того, мы не использовали дополнительное пространство, сохраняя сложность пространства в лучшем виде, то есть O (1).
Заключение
Мы обсудили три подхода к проблеме улавливания дождевой воды.
Подход грубой силы использовал два вложенных цикла и постоянное пространство. Мы нашли решение, найдя левое и правое максимальные значения каждого элемента.
Затем мы использовали два массива для хранения наших левых и правых максимальных значений и уменьшили нашу временную сложность до O(n).
В последнем подходе мы использовали два указателя, а также уменьшили нашу пространственную сложность до O(1).
А теперь давайте выпьем чаю и будем гордиться тем, что нам удалось поймать максимальное количество воды, которое мы смогли с данной нам местностью.