Улавливание дождевой воды

Давайте разберемся в проблеме

Учитывая n неотрицательных целых чисел, представляющих карту высот, где ширина каждой башни равна 1, напишите программу, чтобы вычислить, сколько воды она может уловить после дождя.

Пример 1

Input: height[] = [2, 0, 1, 0, 2], Output: 5
Explanation: 
Trapped water = 2 x 1 + 1 x 1 + 2 x 1 = 5 (Area of the blue region in the following diagram)

Пример 2

Input: height[] = [0,1,0,2,1,0,1,3,2,1,2,1], Output: 6
Explanation: 
Trapped water = 1 x 1 + 1 x 1 + 2 x 1 + 1 x 1 + 1 x 1 = 6 (Area of the blue region in the following diagram)

Важное примечание. Прежде чем переходить к решениям, мы рекомендуем учащимся решить эту проблему. Если решено, то молодец! Хотелось бы услышать ваши идеи в комментарии. В противном случае никаких проблем, это возможность научиться новому подходу к решению проблем. Думай и наслаждайся :)

Обсуждаемые подходы к решению

1. Решение грубой силы с использованием вложенных циклов
2. Решение с использованием дополнительной памяти: динамическое программирование
3. Решение с использованием структуры данных: Стек
4. Эффективное решение с использованием одного сканирования: два указателя

1. Решение методом грубой силы с использованием вложенных циклов

Идея алгоритма

Одна из основных идей заключается в сканировании массива height [] и суммировании воды, удерживаемой в каждой башне. Высота воды, удерживаемой на любой высоте башни [i] = минимальная или максимальная высота башен с обеих сторон минус ее высота, т. Е. min (максимальная высота башни слева, максимальная высота башни в справа) - высота [i]

Шаги алгоритма

• Мы объявляем и инициализируем переменную trappedWater для хранения общего количества захваченной воды.
• Теперь просканируйте высоту [] от i = 0 до n-1. Внутри цикла мы объявляем и инициализируем переменные left_maxHeight и right_maxHeight для хранения максимальной высоты башни по обе стороны от текущей башни.
• Для каждой высоты [i] башни мы вычисляем максимальную высоту башни от текущего индекса i до левого края. Мы сохраняем это значение в переменной left_maxHeight.

for(int k = i; k >= 0; k = k - 1)
{
    left_maxHeight = max(height[k], left_maxHeight)
}

• Для каждой высоты [i] башни мы вычисляем максимальную высоту башни от текущего индекса i до правого конца. Мы сохраняем это значение в переменной right_maxHeight.

for(int j = i; j < n; j = j + 1)
{
    right_maxHeight = max(height[j], right_maxHeight)
}

• Теперь мы обновляем общее количество воды, используя приведенную выше формулу.

trappedWater 
= trappedWater + min(left_MaxHeight, right_maxHeight) - height[i]

• По окончании вышеуказанного цикла мы возвращаем значение переменной trappedWater.

Программирование псевдокода

int rain_water_trapping(int height[], int n)
{
    if(n <= 2)
        return 0
    int trappedWater = 0
    for(int i = 0; i < n; i = i + 1)
    {
        int left_maxHeight = 0 , right_maxHeight = 0
        for(int k = i; k >= 0; k = k - 1)
        {
            left_maxHeight = max(height[k], left_maxHeight)
        } 
        for(int j = i; j < n; j = j + 1)
        {
            right_maxHeight = max(height[j], right_maxHeight)
        }
        trappedWater = trappedWater + 
                   min(left_maxHeight, right_maxHeight) - height[i]
    }
    return trappedWater
}

Анализ сложности времени и пространства

Мы используем вложенные циклы, в которых внешний цикл сканирует массив height [], а два внутренних цикла находят right_maxHeight и left_maxHeight. Таким образом, на каждой итерации внешнего цикла мы просматриваем каждый элемент через внутренние циклы. Сложность времени = O (n * n) = O (n²), сложность пространства = O (1)

2. Решение с использованием дополнительной памяти: динамическое программирование.

Идея алгоритма

Можем ли мы еще больше повысить эффективность и решить проблему за O (n)? Можно ли удалить отдельный внутренний цикл для поиска left_maxHeight и right_maxHeight? Давай подумаем!

Если значения left_maxHeight и right_maxHeight известны для каждой башни, мы можем решить эту проблему за одно сканирование массива height [i]. Но как это сделать? Одна из идей - предварительно вычислить left_maxHeight и right_maxHeight для каждой высоты башни [i] и сохранить их в отдельной дополнительной памяти.

Предположим, мы берем left [n] и right [n] для хранения значений, где: left [i] = left_maxHeight высоты башни [ i], right [i] = right_maxHeight высоты башни [i]

Можем ли мы выполнить предварительную обработку и сохранить значения за линейное время? Вот идея:

• Предположим, мы знаем значение left [i-1], тогда мы можем легко вычислить left [i] в ​​O (1). Вот формула = ›left [i] = max (left [i-1], height [i]) (Think)
• Точно так же, если мы знаем значение right [i + 1], мы можем легко вычислить right [i] в ​​O (1). Вот формула = ›right [i] = max (right [i + 1], height [i]) (Think)

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

Шаги алгоритма

• Создаем два массива left [n] и right [n]
• Теперь запустите цикл слева направо и заполните массив left [n]. На каждой итерации i мы сохраняем максимальный элемент, который произошел до этой точки, в left [i]. (Подумайте!)

left[0] = height[0]
for(int i = 1; i < n; i = i + 1)
{
    left[i] = max(left[i-1], height[i])
}

• Точно так же запустите цикл справа налево и заполните массив right [n]. На каждой итерации i запоминайте максимальный элемент, возникший до этой точки в right [i]. (Подумайте!)

right[n-1] = height[n-1]
for(int i = n-2; i >= 0; i = i - 1)
{
    right[i] = max(right[i+1], height[i])
}

• Теперь пройдемся по массиву height [] и вычислим общее количество воды.

int trappeWater = 0
for(int i = 0; i < n; i = i + 1)
{
    trappedWater = trappedWater + min(left[i], right[i]) - height[i]
}

• Вернуть значение, хранящееся в переменной trappedWater.

Программирование псевдокода

int rain_water_trapping(int height[], int n)
{
    if(n <= 2)
        return 0
    int left[n], right[n]
    left[0] = height[0]
    for(int i = 1; i < n; i = i + 1)
    {
        left[i] = max(left[i-1], height[i])
    }
 
    right[n-1] = height[n-1]
    for(int i = n-2; i >= 0; i = i - 1)
    {
        right[i] = max(right[i+1], height[i])
    }
  
    int trappeWater = 0
    for(int i = 0; i < n; i++)
    {
        trappedWater = trappedWater + 
                       min(left[i], right[i]) - height[i]
    }
    return trappedWater
}

Анализ сложности времени и пространства

В приведенном выше псевдокоде мы запускаем три независимых цикла размера n. Чтобы найти right_maxHeight и left_maxHeight, мы использовали два отдельных цикла. И для обхода массива мы также использовали один цикл. Итак, Сложность времени = O (n) + O (n) = O (n).

Мы использовали два дополнительных массива размера n. Итак, Сложность пространства = O (n) + O (n) = O (n)

3. Решение с использованием структуры данных: стек

Можем ли мы решить эту проблему за одно сканирование? Давайте изучим.

• Площадь области 1 = область, ограниченная индексом 2 и 0
• Площадь области 2 = область, ограниченная индексом 5 и 3.
• Площадь области 3 = область, ограниченная индексом 6 и 3.
• Площадь области 4 = область, ограниченная индексом 6 и 2.
• Площадь области 5 = область между индексами 8 и 6
• Площадь области 5 = область между индексами 9 и 6

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

Шаги алгоритма

• Мы объявляем стек S для хранения индексов башен.
• Теперь мы сканируем высоту [n] с помощью переменной цикла curr ‹n.
• Если мы нашли текущую башню больше, чем эта башня наверху стека, мы можем сказать, что башня на вершине стека ограничена между текущей башней и предыдущей башней в стеке. Следовательно, мы выдвигаем штабель и добавляем воду, оставшуюся между башнями, к общему количеству удерживаемой воды. Мы можем продолжать этот шаг в цикле, пока не найдем текущую башню меньше, чем башня на вершине стека.
• Вода, застрявшая между башнями = Площадь прямоугольной области, образованной текущей башней, выскочившей башней и башней наверху стопки.

Длина области = (текущий индекс - индекс верхнего элемента стека - 1)

Высота области = min (высота текущей башни, высота башни наверху стека) - высота всплывающей башни

Захваченная вода = длина области x высота области

• Если текущая башня меньше или равна башне наверху стека, мы помещаем индекс текущей башни в стек и переходим к следующей башне. Это означает, что текущая башня ограничена башней наверху стека.

Программирование псевдокода

int rain_water_trapping(int height[], int n)
{
    int trappeWater = 0, curr = 0
    stack S
    while (curr < n)
    {
        while (!S.empty() && height[curr] > height[S.top()])
        {
            int top_tower = S.Pop()
            if (S.empty())
                break
            int region_length = curr - S.top() - 1
            int region_height = min(height[curr], height[S.top()]) 
                                - height[top_tower]
            trappedWater = trappedWater + 
                           region_length * region_height
        }
        S.push(curr)
        curr = curr + 1
    }
    return trappedWater
}

Примечание. Если (height [curr] ›height [S.top ()]), то башня наверху стопки меньше, чем предыдущая башня в стопке и текущая башня. В таком сценарии он образует окрашенную прямоугольную область, а захваченная вода равна площади этой области.

Анализ сложности времени и пространства

Мы делаем однократный обход массива height []. В худшем случае мы обрабатываем каждую башню дважды, используя стек, то есть одну операцию push () и одну операцию pop (). (Подумайте!) Операции push () и pop () в худшем случае занимают O (1) раз. Итак, сложность времени = O (n).

В худшем случае стек может занимать до n элементов. Сложность пространства = O (n)

4. Эффективное решение с использованием одного сканирования: два указателя.

Идея алгоритма

В последних двух подходах мы используем дополнительные пробелы, чтобы получить решение. Можем ли мы решить эту проблему за одно сканирование, не занимая лишнего места? Давай исследуем!

Основываясь на формуле, использованной во втором подходе, вода, захваченная любой башней, зависит от минимальной или максимальной высоты башен с обеих сторон. Итак, вместо того, чтобы поддерживать два массива размера n для хранения left_maxHeight и right_maxHeight, можем ли мы поддерживать две переменные для хранения максимума до заданной точки? Считать!

Предположим, мы ищем как слева, так и справа, сохраняя два указателя left и right отдельно. Если на правом конце есть более крупная башня, то удерживаемая вода будет зависеть от высоты башни в направлении от левого к правому. . Точно так же, если башня на правом конце меньше, то захваченная вода будет зависеть от высоты башни в направлении от справа к слева . (Считать!)

int trappedWater = 0
int left_maxHeight = 0, right_maxHeight = 0
int left = 0, right = n - 1

if (height[left] < height[right])
{
    if (height[left] > left_maxHeight)
        left_maxHeight = height[left]
    else
        trappedWater = trappedWater + left_maxHeight - height[left]
    left = left + 1
}

if (height[left] > height[right])
{
    if (height[right] > right_maxHeight)
        right_maxHeight = height[right]
    else
        trappedWater = trappedWater + right_maxHeight 
                                    - height[right]
    right = right - 1
}

int rain_water_trapping(int height[], int n)
{
    int trappedWater = 0
    int left_maxHeight = 0, right_maxHeight = 0
    int left = 0, right = n - 1
    while (left <= right)
    {
        if (height[left] < height[right])
        {
            if (height[left] > left_maxHeight)
                left_maxHeight = height[left]
            else
                trappedWater = trappedWater + left_maxHeight 
                                            - height[left]
            left = left + 1
        }
        else
        {
            if (height[right] > right_maxHeight)
                right_maxHeight = height[right]
            else
                trappedWater = trappedWater + right_maxHeight 
                                            - height[right]
            right = right - 1
        }
    }
    return trappedWater
}