Количество дождевой воды
Published: 2023-11-25 22:38:22


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

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

![](https://cdn-images-1.medium.com/max/2000/1*HApgOIS7L0N6XiFFo2dPyA.png)

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

![](https://cdn-images-1.medium.com/max/2000/1*8QkPCCnv7IL3jtk7RqD43g.png)

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

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

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

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

![](https://cdn-images-1.medium.com/max/2000/1*b3IKpCuzwJ--P43pUb47-Q.png)

На картинке я **текущую точку выделил желтым цветом**. **А максимумы слева и справа красным цветом.**
>  **Тогда уровень воды будет равен минимуму из максимумов слева и справа от текущей точки.**

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

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

![](https://cdn-images-1.medium.com/max/2018/1*82efm1UXNmAnPXwjOFv5gw.png)

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

![](https://cdn-images-1.medium.com/max/2112/1*Tdypy2i8gj4P1IqyXFg-ZA.png)

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

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

![](https://cdn-images-1.medium.com/max/2388/1*MbH9ufDp9XcnWwikhSnXYQ.png)

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

```java
    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).