2021/05/06
维护一个单调递减栈。这个栈存放柱子的下标，根据柱子的高度单调递减。
如图所示，i 是当前考察的柱子，top 指向栈顶，left 指向栈顶弹出后的下一个栈顶。
每当遇到一个高度大于 top 的柱子时，我们从栈顶一个一个的向左注水。
每遇到一根柱子，都从栈顶开始，消除高度小于等于他的柱子。
class Solution {
public int trap(int[] height) {
LinkedList<Integer> stk = new LinkedList<>();
int res = 0;
for (int i = 0; i < height.length; i++) {
while (!stk.isEmpty() && height[i] > height[stk.peek()]) {
int top = stk.pop();
if (stk.isEmpty()) break;
int left = stk.peek();
int w = i - left - 1;
int h = Math.min(height[i], height[left]) - height[top];
res += w * h;
}
// 此时要么栈为空，要么当前元素小于栈顶元素
stk.push(i);
}
return res;
}
}