Улавливание дождевой воды — очень известная задача массивов и динамического программирования. Это сложная задача как для 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;

Сохраните воду в переменной результата.

Теперь, помня об этих переменных, давайте посмотрим на следующие вещи:

  1. Блок на высоте[слева] будет хранить воду только в том случае, если у него есть блок выше него с обеих сторон. Таким образом, мы должны выполнить два условия для блока на 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).

А теперь давайте выпьем чаю и будем гордиться тем, что нам удалось поймать максимальное количество воды, которое мы смогли с данной нам местностью.