Количество дождевой воды

Ссылка на leetcode: https://leetcode.com/problems/trapping-rain-water/description/

Условие. Дан массив целых чисел. Каждое число отображает высоту рельефа в данной точке. Например, дан массив: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]. Такой рельеф можно представить так:

Теперь представим, что сверху льют воду/идет дождь. Нужно вычислить, сколько накопится воды. Для приведенного рельефа ответ 6:

Решение. Давайте подумаем сколько воды накопится для какой-то конкретной точки. Рассмотрим точку i = 6, heights[6] = 1. Уровень воды в данной точки интуитивно равен 2. Соответственно, количество воды в данной точке 2 — heights[6] = 2–1 = 1. Чтобы получить общее количество воды нужно просуммировать это количество для каждой точки: sum(waterLevel[i] — heights[i]).

Хорошо, но как формально вычислить этот уровень воды для каждой конкретной точки?

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

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

На картинке я текущую точку выделил желтым цветом. А максимумы слева и справа красным цветом.

Тогда уровень воды будет равен минимуму из максимумов слева и справа от текущей точки.

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

Давайте объявим два массива. Значения в первом массиве maxToLeft[i] равны максимуму высоты рельефа слева от точки i.

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

Уровень воды в точке i равен level = min(maxToLeft[i], maxToRight[i]).

Если уровень воды превышает текущую высоту, то вычисляем количество воды как level — heights[i].

Окончательно в коде:

    class Solution {
        public int trap(int[] height) {
            int[] maxToLeft = new int[height.length];
            //Вычиляем максимальную высоту слева от текущей точки
            for (int i = 1; i < height.length; i++) {
                maxToLeft[i] = Math.max(maxToLeft[i - 1], height[i - 1]);
            }
            //Вычисляем максимальную высоту справа от текущей точки
            int[] maxToRight = new int[height.length];
            for (int i = height.length - 2; i >= 0; i--) {
                maxToRight[i] = Math.max(maxToRight[i + 1], height[i + 1]);
            }
            int water = 0;
            for (int i = 0; i < height.length; i++) {
                //Уровень воды в текущей точке равен минимуму 
                //от максимальных высот слева и справа
                int level = Math.min(maxToLeft[i], maxToRight[i]);
                //Если уровень воды больше текущей высоты, то вычисляем разницу,
                //между уровнем воды и текущей высотой. 
                //Столько воды будет в текущей точке.
                if (level > height[i]) {
                    water += (level - height[i]);
                }
            }
            return water;
        }
    }

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