分析

根据题目所说，要统计雨水的体积，实际是统计雨水的面积，要考虑到左右两边柱子的高低。

实例1：

输入： height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出： 6

解释： 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

题解

暴力

对于下标 $i$ 的柱子： 这个位置能接住的雨水高度 = 左右两侧最高柱子中较矮的那一根高度 - 当前柱子高度

val = min(leftMax, rightMax) - height[i]

• 如果 $val > 0$ ：可以积水，加上该水量；
• 如果 $val \le 0$：当前柱子高于两侧矮边的最大值，存不住水，积水为0。

代码

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int n = height.size();
        for(int i = 1; i < n - 1; i++) {
            int lmax = 0, rmax = 0;
            for(int j = 0; j < i; j++) lmax = max(lmax, height[j]);
            for(int j =  i + 1; j < n; j++) rmax = max(rmax, height[j]);
            int val = min(lmax, rmax) - height[i];
            if(val > 0) res += area;
        }
        return res;
    }
};

时间复杂度 $O(n^2)$

提交到力扣上面会超时，所以要采用一下解法。

双指针

双指针用两个变量动态保存左侧历史最大值lMax、右侧历史最大值rMax。

规则：

1. 左指针l在最左、右指针r在最右；
2. 哪边柱子高度更小，哪边就是决定水位的短板，只处理这一侧；
   • 若height[l] < height[r]：水位由左侧最高墙lMax决定；
   • 若height[r] <= height[l]：水位由右侧最高墙rMax决定；
3. 当前柱子高度 $\ge$ 历史最高墙：存不住水，更新最高墙；
4. 当前柱子高度 $\lt$ 历史最高墙：可以蓄水，累加水量。

左右指针同时起到遍历的作用。

代码

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int lMax = 0, rMax = 0;
        int res = 0;
        while(l < r) {
            if(height[l] < height[r]) {
                if(height[l] >= lMax) lMax = height[l];
                else res += lMax - height[l];
                l++;
            } else {
                if(height[r] >= rMax) rMax = height[r];
                else res += rMax - height[r];
                r--;
            }
        }
        return res;
    }
};

时间复杂度 $O(n)$

DP

DP 核心思想

单个位置 $i$ 蓄水量公式： water[i] = min(leftMax[i], rightMax[i]) - height[i]

• leftMax[i]：下标 $i$ 左侧所有柱子的最大高度（包含 $i$ ）
• rightMax[i]：下标 $i$ 右侧所有柱子的最大高度（包含 $i$ ）

DP做法分三步：

1. 正向遍历数组，算出leftMax[]；
2. 反向遍历数组，算出rightMax[]；
3. 遍历每个位置，通用公式累加雨水。

递推公式

$leftMax[i] = max(leftMax[i-1], height[i])$

$rightMax[i] = max(rightMax[i+1], height[i])$

代码

class Solution {
public:
    int trap(vector<int>& height) {
       int n = height.size();
       if (n == 0) return 0;
       vector<int> leftMax(n), rightMax(n);
       leftMax[0] = height[0];
       for(int i = 1; i < n; i++) leftMax[i] = max(leftMax[i - 1], height[i]);
       rightMax[n - 1] = height[n - 1];
       for(int i = n - 2; i >= 0; i--) rightMax[i] = max(rightMax[i + 1], height[i]);
       int res = 0;
       for(int i = 0; i < n; i++) res += min(leftMax[i], rightMax[i]) - height[i];
       return res;
    }
};

时间复杂度 $O(n)$，这是典型的空间换时间。

单调栈

前面DP、双指针都是竖着算：对每个位置，看上下能存多高的水。 单调栈是横着算：一层一层横向计算凹槽的积水面积。 栈中存放柱子下标，维持规则：栈内对应的高度严格递减。 一旦遇到一根更高的柱子，说明形成了凹槽，可以借助雨水，弹出栈顶作为凹槽底部，计算积水宽度与高度。

积水计算公式

弹出凹槽底部下标bottom后：

1. 栈不为空：左边界 = 栈顶下标left
2. 右边界 = 当前下标i
3. 积水宽度：width = i - left - 1
4. 积水高度：h = min(height[left], height[i]) - height[bottom]
5. 本次积水体积：width * h

代码

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int res = 0;
        int n = height.size();
        for(int i = 0; i < n; i++) {
            while(!st.empty() && height[i] > height[st.top()]) {
                int bottom = st.top();
                st.pop();
                if(st.empty()) break;
                int left = st.top();
                int width = i - left - 1;
                int h = min(height[left], height[i]) - height[bottom];
                res += width * h;
            }
            st.push(i);
        }
        return res;
    }
};

1.为什么栈存下标而不是高度？

既要拿到高度比较大小，又要用下标计算凹槽的宽度。

2.弹出元素后栈为空就break？

凹槽必须左右都有围墙才能存水。如果弹出底部后栈空，左边没有围墙，无法蓄水。

3.栈始终保持递减

只有更高的柱子到来时才结算积水，符合”两边高、中间低才能存水“的物理规则。

时间复杂度 $O(n)$：每个下标只会入栈一次、出栈一次； 空间复杂度 $O(n)$：最坏情况严格递减数组，所有元素进栈。

总结

上述题解的核心都是： val = min(leftMax, rightMax) - height[i]

四种方法对比

解法	计算方式	时间	空间	特点
暴力	纵向逐点遍历	$O(n^2)$	$O(1)$	最简单，会超时
双指针	纵向、双指针动态维护最值	$O(n)$	$O(1)$	最优，面试推荐
DP	纵向、预处理左右最大数组	$O(n)$	$O(n)$	易懂，空间换时间
单调栈	横向逐层计算积水	$O(n)$	$O(n)$	单调栈经典题型

42. 接雨水 - 力扣（LeetCode）