LeetCode.042.Trapping Rain Water 接雨水

题目描述

42 Trapping Rain Water
https://leetcode-cn.com/problems/trapping-rain-water/

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

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

---

相似题目

LeetCode.739.Daily Temperatures 每日温度
LeetCode.042.Trapping Rain Water 接雨水
LeetCode.084.Largest Rectangle in Histogram 柱状图中最大的矩形

LeetCode.011.Container With Most Water 盛最多水的容器

---

解题过程

暴力搜索O(n^2)

最朴素的做法，对每个直方图，找到左右最大值，min(leftMax, rightMax) 和 当前值的差就是当前直方图能接住的雨水。
时间复杂度 O(n^2)，空间复杂度 O(1)

private static class SolutionV2020 {
    public int trap(int[] height) {
        if (null == height || height.length < 3) {
            return 0;
        }
        int leftMax = height[0];
        int res = 0;
        for (int i = 1; i < height.length; i++) {
            if (height[i] >= leftMax) {
                leftMax = height[i];
                continue;
            }
            int rightMax = 0;
            for (int j = i+1; j < height.length; j++) {
                rightMax = Math.max(rightMax, height[j]);
                if (rightMax >= leftMax) {
                    break;
                }
            }
            // 找到左右最大值，min(leftMax, rightMax) 和 当前值的差就是当前直方图能接住的雨水
            if (Math.min(leftMax, rightMax) > height[i]) {
                res += Math.min(leftMax, rightMax) - height[i];
            }
            leftMax = Math.max(leftMax, height[i]);
        }
        return res;
    }
}

用数组保存往前/后的最大值O(n)

稍微深入想一下，可以用2个数组保存当前位置i往前和往后的最大值，把时间复杂度降到 O(n)，空间复杂度升为O(n)
再深入想一下，只需要一个保存当前位置i往后最大值的数组即可，往前的最大值可以在遍历过程中用一个变量保存。

单调递减栈

维护一个单调递减栈，栈中存放数组元素的下标，栈为空或当前元素小于栈顶时入栈。
当前元素大于栈顶时，说明形成了一个“凹”槽，可以接住水了，把栈顶出栈记为 bottom，栈顶元素就是凹槽的底，找到凹槽的左右边界，左边界就是新的栈顶 height[stack.top]，右边界就是当前元素 height[current] ，计算这个凹槽可接住的水量：
雨水条块的高度 = min(height[stack.top], height[current]) - height[bottom]
雨水条块的宽度 = current - stack.top - 1
接住的水量 = 雨水条块的高度 × 雨水条块的宽度

单调栈解法和暴力搜索法有根本的不同：

• 暴力搜索法每次计算当前位置 current 上能够接住的水量，是一个竖着的条块。
• 单调栈法每次计算两个边界之间的水量，是一个横着的条块。

---

GitHub代码

algorithms/leetcode/leetcode/_042_TrappingRainWater.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_042_TrappingRainWater.java

---