题目——接雨水
/**
* Created with IntelliJ IDEA.
* Description:
* User: CDz
* Create: 2020-04-04 22:38
* 42. 接雨水
* 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
* <p>
* <p>
* <p>
* 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
* <p>
* 示例:
* <p>
* 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
* 输出: 6
**/
思路笔记
单调栈解答
public int trap(int[] height) {
if (height.length == 0) return 0;
Stack<Integer> stack = new Stack<>();
int ans = 0;
for (int i = 0; i < height.length; i++) {
//curr 遍历值大于 栈里新添加的最新元素
while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
//弹出栈中最新的值
int curIdx = stack.pop();
while (!stack.isEmpty()&&height[stack.peek()]==height[curIdx]){
//如果有相等的高度继续弹出
stack.pop();
}
if (!stack.isEmpty()){
Integer stackTop = stack.peek();
//计算宽度
//stackTop 为 left左柱子
//height[i]为right右柱子
//高度为：min(left,right)
//宽度为：i-stackTop-1 水的宽度是 左右柱子不算在内的，即为左右柱子中间的宽度
ans+=(Math.min(height[stackTop],height[i])-height[curIdx])*(i-stackTop-1);
}
}
stack.add(i);
}
return ans;
}
