42. Trapping Rain Water

, ,

Violence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 - 1; j >= 0; j--) {
                leftMax = Math.max(height[j], leftMax);
            }
            // 向右扫描找到右侧最高的柱子（不含当前柱子）
            for (int j = i + 1; j < height.length; j++) {
                rightMax = Math.max(height[j], rightMax);
            }

            int minMax = Math.min(leftMax, rightMax);
            if (minMax > height[i]) {
                res += minMax - height[i];
            }
        }

        return res;
    }
}

Violence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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);
            }

            // 左右侧最高的柱子其中较低的那个柱子决定当前柱子能够接多少雨水，一定要记住减去当前柱子的高度才能得到当前柱子所在位置可以接的雨水数量
            // 因为 leftMax >= height[i] && rightMax >= height[i]，所以此处无需像上方解法一样判断小于 0
            res += Math.min(leftMax, rightMax) - height[i];
        }

        return res;
    }
}

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int trap(int[] height) {
        int[] leftMax = new int[height.length]; // 左侧柱子的最大高度，不包含当前柱子
        for (int i = 1; i < height.length; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
        }

        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]);
        }

        int water = 0;

        // 两侧端点无法接雨水，遍历时不处理这两个端点
        for (int i = 1; i < height.length - 1; i++) {
            int min = Math.min(leftMax[i], rightMax[i]);
            water += Math.max(0, min - height[i]);
        }

        return water;
    }
}

Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
    }
}

栈中不存储相同的高度也能 AC，详见下方解法。

Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int trap(int[] height) {
        int water = 0;
        
        Stack<Integer> decreaseStack = new Stack<>(); // 严格单调递减栈，栈中存储的为索引
        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 width = i - leftIndex-1;
                
                int leftHeight = height[leftIndex];
                water += (Math.min(leftHeight, height[i]) - midHeight) * width;
            }

            decreaseStack.push(i);
        }

        return water;
    }
}

Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int trap(int[] height) {
        int water = 0;

        int leftMax = 0, rightMax = 0; // 不包含当前柱子的最大高度
        int i = 0, j = height.length - 1;
        while (i <= j) { // 注意此处是小于等于，当 i == j 时也需要计算
            if (leftMax <= rightMax) {
                // 左侧柱子更低，此时可以计算 i 处索引可以接的雨水，而不能计算 j 处索引可以接的雨水，因为 [i + 1, j - 1] 中可能有更高的柱子
                water += Math.max(0, leftMax - height[i]); // 注意是左侧柱子高度减去当前柱子高度
                leftMax = Math.max(leftMax, height[i++]);
            } else {
                // 右侧柱子更低，此时可以计算 j 处索引可以接的雨水，而不能计算 i 处索引可以接的雨水，因为 [i + 1, j - 1] 中可能有更高的柱子
                water += Math.max(0, rightMax - height[j]); // 注意是右侧柱子高度减去当前柱子高度
                rightMax = Math.max(rightMax, height[j--]);
            }
        }

        return water;
    }
}

Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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) { // 注意此处是小于等于，当 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;
    }
}

References

42. Trapping Rain Water
官方题解看不懂? 双指针解法的清晰说明
面试题 17.21. 直方图的水量