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

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

Пример:

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

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

1⃣Найдите максимальную высоту столбца с левого конца до индекса i в массиве left_max.

2⃣Найдите максимальную высоту столбца с правого конца до индекса i в массиве right_max.

3⃣Итерируйте по массиву высот height и обновляйте ans: добавьте min(left_max[i], right_max[i]) - height[i] к ans.

😎 Решение:

class Solution {
    public int trap(int[] height) {
        if (height.length == 0) return 0;
        int ans = 0;
        int size = height.length;
        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;
    }
}

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