题目描述
思路一：单调栈
柱子的高度递减的时候是装不了水的，当碰到第一个比之前高的柱子才可以装水。
此时计算栈顶索引能装的水：
- 宽：i - left - 1(这个left为栈顶元素pop之后的peek值)
- 高：min(height[left], height[i]) - height[top]
- 该题维护的是一个单调递减栈
方法一：对应思路一
class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) return 0;
// 这里维护的是一个单调递减栈
Deque<Integer> stack = new ArrayDeque<>();
int res = 0;
for (int i = 0; i < height.length; i ++) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
// 这行代码正好能解决示例1中索引0为0的情况
if (stack.isEmpty()) break;
int h = Math.min(height[i], height[stack.peek()]) - height[top];
int w = i - stack.peek() - 1;
res += h * w;
}
stack.push(i);
}
return res;
}
}