脚本宝典收集整理的这篇文章主要介绍了每日一题:42. 接雨水,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
单调栈问题 具体可以看题解的动画演示 https://leetcode-cn.COM/PRoblems/trapping-rain-water/solution/yi-miao-jiu-neng-du-dong-de-dong-hua-jie-o9sv/
class Solution {
public int trap(int[] height) {
if (height.length<3){
return 0;
}
int ans = 0;
//记录下标
LinkedList<Integer> stack = new LinkedList<>();
for (int i=0;i<height.length;i++){
if (stack.iSEMpty()){
stack.add(i);
}else {
//保持单调递减的栈
if (height[i]<=height[stack.getLast()]){
stack.add(i);
}else {
while (!stack.isEmpty() && height[i]>height[stack.getLast()]){
//当前栈顶的高度
int h = height[stack.getLast()];
stack.removeLast();
if (stack.isEmpty()){
break;
}
//取两者高度差的较小值
int n = Math.min(height[i]-h,height[stack.getLast()]-h);
//两点的下标距离
int index = i - stack.getLast()-1;
ans += n*index;
}
stack.add(i);
}
}
}
return ans;
}
}
以上是脚本宝典为你收集整理的每日一题:42. 接雨水全部内容,希望文章能够帮你解决每日一题:42. 接雨水所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。