题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 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 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length1 <= n <= 2 * 10^40 <= height[i] <= 10^5
分析1（单调栈）
单调栈就是其中的数据不断递增或者不断减小的一种栈结构。
java官方推荐使用 Deque<Integer> st = new ArrayDeque<>(); 来构建一个栈，并不推荐使用 Stack 来创建一个栈结构。
思路
对于接雨水问题，我们维护一个单调递减栈，栈中存放的是柱子的下标，对应的高度从栈底到栈顶递减（下标递增而其中下标所对应的高度在递减）。
为什么是递减？因为我们需要找到凹槽：左边高、中间低、右边高。当遍历到当前柱子 i 时，如果它的高度大于栈顶柱子的高度，说明栈顶柱子可能是凹槽底部，而当前柱子是右边界，栈顶下面的那个柱子是左边界。
单调栈接雨水可以理解为“横着一条一条地算”，也就是按水平层累加雨水。
具体过程
-
遍历每个柱子
i，高度为h = height[i]。 -
当栈不为空且
height[st.peek()] <= h时：- 弹出栈顶
bottom作为凹槽底部，bottomH = height[bottom]。 - 如果弹出后栈为空，说明没有左边界，不能接水，
break。 - 否则，新栈顶
left就是左边界。 - 水的高度
dh = Math.min(height[left], h) - bottomH。 - 水的宽度
width = i - left - 1。 - 累加
ans += dh * width。
- 弹出栈顶
-
将当前下标
i入栈。
为什么用 <= 而不是 <
当高度相等时，弹出旧的下标，用新的下标作为底部，可以避免重复计算，同时保持栈的严格递减。即使计算出的水高为 0，也不影响最终结果。
解答1
class Solution {
public int trap(int[] height) {
// 单调栈
Deque<Integer> st = new ArrayDeque<>();
// 累计总接雨水量
int ans = 0;
// 遍历每一根柱子，i 既可能作为右边界，也可能作为新的栈元素
for (int i = 0; i < height.length; i++) {
int h = height[i]; // 当前柱子的高度
// 当栈不为空，且栈顶柱子的高度 <= 当前柱子高度时：说明栈顶这个位置可能是一个凹槽的底部
while (!st.isEmpty() && height[st.peek()] <= h) {
// 弹出栈顶，作为凹槽的底部
int bottomH = height[st.pop()];
// 如果弹出后栈为空，说明左边没有更高的柱子当左边界，水会流走，无法接水，直接结束本次 while。
if (st.isEmpty()) {
break;
}
// 此时新的栈顶就是左边界下标
int left = st.peek();
// 计算这一层水的高度
int dH = Math.min(height[left], h) - bottomH;
// 这一层接水量 = 水高 * 宽度，累加到总答案中
ans += dH * (i - left - 1);
}
// 当前柱子处理完后入栈，作为后面可能用到的左边界或底部
st.push(i);
}
// 返回总接雨水量
return ans;
}
}
复杂度分析
- 时间复杂度：
O(n)，每个下标最多入栈一次、出栈一次。 - 空间复杂度：
O(n)，栈最多存储n个下标。
Deque 的一些用法
Deque 是双端队列，既可以当栈用，也可以当队列用。
Java 中推荐用 ArrayDeque 来实现栈：
Deque<Integer> st = new ArrayDeque<>();
当栈用
Deque<Integer> st = new ArrayDeque<>();
st.push(1); // 入栈，等价于 addFirst
st.pop(); // 出栈，等价于 removeFirst
st.peek(); // 查看栈顶，等价于 peekFirst
st.isEmpty(); // 判断栈是否为空
st.size(); // 栈中元素个数
st.clear(); // 清空栈
当队列用
Deque<Integer> q = new ArrayDeque<>();
q.offer(1); // 入队，等价于 offerLast
q.poll(); // 出队，等价于 pollFirst
q.peek(); // 查看队首，等价于 peekFirst
q.isEmpty(); // 判断队列是否为空
示例
数组：
height = [3, 2, 1, 0, 1, 2, 3]
// 下标： 0 1 2 3 4 5 6
模拟过程：
| i | h | 操作 | 栈（栈底 → 栈顶） | 本次接水 | ans |
|---|---|---|---|---|---|
| 初始 | - | - | [] |
- | 0 |
| 0 | 3 | 入栈 0 | [0(3)] |
0 | 0 |
| 1 | 2 | 入栈 1 | [0(3), 1(2)] |
0 | 0 |
| 2 | 1 | 入栈 2 | [0(3), 1(2), 2(1)] |
0 | 0 |
| 3 | 0 | 入栈 3 | [0(3), 1(2), 2(1), 3(0)] |
0 | 0 |
| 4 | 1 | 弹出 3(0)，左边界 2(1)，接水 1；弹出 2(1)，水高 0；入栈 4 |
[0(3), 1(2), 4(1)] |
1 | 1 |
| 5 | 2 | 弹出 4(1)，左边界 1(2)，接水 3；弹出 1(2)，水高 0；入栈 5 |
[0(3), 5(2)] |
3 | 4 |
| 6 | 3 | 弹出 5(2)，左边界 0(3)，接水 5；弹出 0(3)，栈空 break；入栈 6 |
[6(3)] |
5 | 9 |
分析2（双指针）
这个与单调栈不同，单调栈为“横着一条一条地算”，而双指针的方法为竖着一列一列地算。
我个人感觉双指针要比单调栈好懂得多了。
思路
对于每一个柱子 i，它能接的雨水量取决于：
min(左边最高柱子, 右边最高柱子) - height[i]
如果这个值大于 0，就是这一列能接的水；否则接不了水。
双指针的做法是：用 left 和 right 从两端向中间移动，同时维护两个变量：
leftMax：从最左边到left扫描过的最高柱子高度；rightMax：从最右边到right扫描过的最高柱子高度。
关键点在于：我们不需要同时知道左边最高和右边最高，只需要知道较矮的那一边的最高值，就可以确定当前列的接水量。
为什么？
当 leftMax < rightMax 时，对于 left 位置来说：
- 它左边最高是
leftMax； - 它右边一定存在一个高度至少为
rightMax的柱子（因为rightMax是右指针及右侧扫描过的最大值，而leftMax < rightMax）； - 所以
min(左边最高, 右边最高) = leftMax。
因此，left 位置能接的水就是：
leftMax - height[left]
可以放心地计算并移动 left。
反过来，当 rightMax <= leftMax 时，对于 right 位置来说，它右边最高是 rightMax，左边一定存在一个不低于 leftMax 的柱子，所以 min(左边最高, 右边最高) = rightMax。
于是 right 位置能接的水就是：
rightMax - height[right]
计算后移动 right。
解答2
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1; // 左右指针
int leftMax = 0, rightMax = 0; // 已扫描的左右两边最大值
while (left < right) {
// 更新左边扫描过的最高柱子
leftMax = Math.max(leftMax, height[left]);
// 更新右边扫描过的最高柱子
rightMax = Math.max(rightMax, height[right]);
// 如果左边最高小于右边最高，说明 left 位置的水量由 leftMax 决定
if (leftMax < rightMax) {
ans += leftMax - height[left];
left++;
} else {
// 否则 right 位置的水量由 rightMax 决定
ans += rightMax - height[right];
right--;
}
}
return ans;
}
}
复杂度分析
- 时间复杂度：
O(n)，左右指针一共遍历每个柱子一次。 - 空间复杂度：
O(1)，只用了常数个变量。
示例
以 height = [3, 2, 1, 0, 1, 2, 3] 为例：
下标： 0 1 2 3 4 5 6
高度： 3 2 1 0 1 2 3
| 步骤 | left | right | leftMax | rightMax | 比较 | 操作 | ans |
|---|---|---|---|---|---|---|---|
| 初始 | 0 | 6 | 0 | 0 | - | - | 0 |
| 1 | 0 | 6 | 3 | 3 | leftMax < rightMax不成立 |
ans += rightMax - height[6] = 3-3=0，right-- |
0 |
| 2 | 0 | 5 | 3 | 3 | 3 < 3不成立 |
ans += 3 - 2 = 1，right-- |
1 |
| 3 | 0 | 4 | 3 | 3 | 3 < 3不成立 |
ans += 3 - 1 = 2，right-- |
3 |
| 4 | 0 | 3 | 3 | 3 | 3 < 3不成立 |
ans += 3 - 0 = 3，right-- |
6 |
| 5 | 0 | 2 | 3 | 3 | 3 < 3不成立 |
ans += 3 - 1 = 2，right-- |
8 |
| 6 | 0 | 1 | 3 | 3 | 3 < 3不成立 |
ans += 3 - 2 = 1，right-- |
9 |
| 7 | 0 | 0 | - | - | 循环结束 | - | 9 |