题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

1
2
3
输入：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 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

解题思路

单调栈

我们要保持栈内单调递减，栈内存储的元素为 height的下标

stack为栈，x为height中的高度

  1. x < 栈顶高度时，将x对应的下标推入栈中
  2. x == 栈顶高度时，将栈中旧下标弹出，新下标推入栈
  3. x > 栈顶高度时，此时说明有一个凹陷，我们要计算这个凹陷的面积，长方形的面积 = 长 * 宽
    1. 弹出栈顶元素，定义为mid
    2. 计算长方形面积

双指针

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def trap(self, height: List[int]) -> int:
        stack = [0]
        ans, n = 0, len(height)
        for i in range(1, n):
            x = height[i]
            if x < height[stack[-1]]:
                stack.append(i)
                continue
            # 一样的高度取新下表
            elif x == height[stack[-1]]:
                stack.pop()
                stack.append(i)
                continue
            while stack and x > height[stack[-1]]:
                mid = height[stack.pop()]
                if stack:
                    ans += (min(height[stack[-1]], x) - mid) * (i - stack[-1] - 1)
            stack.append(i)
        return ans

C++

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(vector<int>& height) {
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if (stk.empty()) {
                    break;
                }
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }
};