LeetCode 42 接雨水 - 单调栈解法
思路
从“横向”看接雨水：每一层雨水的底都对应数组中的某个高度。
- 因此可以把数组元素视为“底”，并寻找它左侧和右侧第一个更高的边界。
- 这个过程适合用单调栈处理，细节可参考：[01根基](LeetCode/08 单调栈/单调栈基础与模板.md#^zqyyg3)。
public int trap1(int[] height){
int ans = 0;
int n = height.length;
Deque<Integer> deque = new LinkedList<>();
for(int i = 0;i<n;i++){
int h = height[i];
while (!deque.isEmpty()&&h>=height[deque.peek()]) {
// 这里为什么弹出栈,因为栈中的元素都是未被处理的,以后可能
// 作为左边界或者底部的高,
// 但是这个元素不可能作为左边界了,因为右边已经有个比他大的了,
// 也不能作为底部的高, 因为底部德高已经变为min(left,i)
// 而 left又>i, 因此底部的高一定是 left,
int bottomHeight = height[deque.pop()];
if (deque.isEmpty()) {
break;
}
int left = deque.peek();
int gao = Math.min(height[i], height[left])-bottomHeight;
ans+=gao*(i-left+1-2);
}
deque.push(i);
}
return ans;
}