Задача: 42. Trapping Rain Water
Сложность: hard

Дан массив height, где height[i] представляет высоту столбца. Нужно вычислить, сколько воды может удержаться после дождя.

Пример:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]  
Output: 6  

👨‍💻 Алгоритм:

1⃣Создать массив left_max, где left_max[i] — максимальная высота слева до i.

2⃣Создать массив right_max, где right_max[i] — максимальная высота справа до i.

3⃣Для каждого i, вычислить возможный объем воды как min(left_max[i], right_max[i]) - height[i] и суммировать.

😎 Решение:

public class Solution {
    public int Trap(int[] height) {
        if (height.Length == 0) return 0;

        int size = height.Length, ans = 0;
        int[] left_max = new int[size];
        int[] right_max = new int[size];

        left_max[0] = height[0];
        for (int i = 1; i < size; i++) {
            left_max[i] = Math.Max(height[i], left_max[i - 1]);
        }

        right_max[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            right_max[i] = Math.Max(height[i], right_max[i + 1]);
        }

        for (int i = 1; i < size - 1; i++) {
            ans += Math.Min(left_max[i], right_max[i]) - height[i];
        }

        return ans;
    }
}

Ставь 👍 и забирай 📚 Базу знаний