42. Trapping Rain Water

Violence

class Solution {
    public int trap(int[] height) {
        int res = 0;

        // 遍历可以接雨水的柱子，遍历区间为 (0, length - 1) 是因为两个边界是无法接雨水的，会漏
        for (int i = 1; i < height.length - 1; i++) {
            // 找到当前柱子可以接多少雨水
            int leftMax = 0, rightMax = 0;

            // 向左扫描找到左侧最高的柱子
            for (int j = i; j >= 0; j--) {
                leftMax = Math.max(height[j], leftMax);
            }
            // 向右扫描找到右侧最高的柱子
            for (int j = i; j < height.length; j++) {
                rightMax = Math.max(height[j], rightMax);
            }

            // 左右侧最高的柱子其中较低的那个柱子决定当前柱子能够接多少雨水，一定要记住减去当前柱子的高度才能得到当前柱子可以接的雨水数量
            res += Math.min(leftMax, rightMax) - height[i];
        }

        return res;
    }
}

Iterate

class Solution {
    public int trap(int[] height) {
        // 两个边界处的柱子无法接雨水

        // leftMax[i] 为 height[i] 左侧最高的柱子（不含）高度
        int[] leftMax = new int[height.length];
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]); // 注意此处是 height[i - 1]
        }

        // rightMax[i] 为 height[i] 右侧最高的柱子（不含）高度
        int[] rightMax = new int[height.length];
        for (int i = height.length - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]); // 注意此处是 height[i + 1]
        }

        int water = 0;
        for (int i = 1; i < height.length - 1; i++) {
            // 只有非两个边界处的柱子可能接到雨水
            int minHeight = Math.min(leftMax[i], rightMax[i]);
            if (minHeight > height[i]) {
                water += minHeight - height[i];
            }
        }

        return water;
    }
}

Stack

class Solution {
    public int trap(int[] height) {
        // 非严格单调递减栈，允许存在重复的高度，栈中存的为索引，索引对应的高度非严格单调递减
        // 当遇到比栈顶元素更高的柱子时，此时可以接雨水
        Stack<Integer> decreaseStack = new Stack<>();
        
        int water = 0;
        for (int i = 0; i < height.length; i++) {
            while (!decreaseStack.isEmpty() && height[i] > height[decreaseStack.peek()]) {
                int midHeight = height[decreaseStack.pop()]; // 中间这个柱子的高度
                if (decreaseStack.isEmpty()) {
                    // 左侧没有柱子了，此时不能接雨水
                    break;
                }
                int leftIndex = decreaseStack.peek(); // 注意取左侧柱子时无需出栈
                int leftHeight = height[leftIndex];
                int rightHeight = height[i];

                int width = i - leftIndex - 1;
                int h = Math.min(leftHeight, rightHeight) - midHeight;
                water += width * h;
            }

            decreaseStack.push(i);
        }

        return water;
    }
}

Two Pointers

class Solution {
    public int trap(int[] height) {
        int leftMax = 0; // 从左至右截止至当前位置的最高柱子高度，含当前柱子
        int rightMax = 0; // 从右至左截止至当前位置的最高柱子高度，含当前柱子

        int i = 0, j = height.length - 1;

        int water = 0;
        while (i < j) { // 注意此处是小于而不是小于等于，避免重复计算
            leftMax = Math.max(leftMax, height[i]);
            rightMax = Math.max(rightMax, height[j]);

            if (leftMax <= rightMax) {
                // 左侧最高的柱子更低，此时 i 处能接的雨水取决于左侧柱子
                water += leftMax - height[i++];
            } else {
                // 右侧最高的柱子更低，此时 j 处能接的雨水取决于右侧柱子
                water += rightMax - height[j--];
            }
        }

        return water;
    }
}

Reference

42. Trapping Rain Water
官方题解看不懂? 双指针解法的清晰说明