用个单调栈
提交代码
class Solution {
public int trap(int[] height) {
Stack<Integer> hStack=new Stack<Integer>();
Stack<Integer> pStack=new Stack<Integer>();
int hLeft=0,base=0,water=0;
for(int i=0;i<height.length;i++) {
if(hStack.isEmpty()||hStack.peek()>height[i]) {
hStack.push(height[i]);
pStack.push(i);
}else {
while(!hStack.isEmpty()&&hStack.peek()<=height[i]) {
base=hStack.pop();
pStack.pop();
if(hStack.isEmpty()) break;
hLeft=hStack.peek();
water+=(Math.min(hLeft, height[i])-base)*(i-pStack.peek()-1);
}
hStack.push(height[i]);
pStack.push(i);
}
}
return water;
}
}