这雨水接住了，offer就拿到了
时间：2020-11-25 16:43:28
手机看文章
扫描二维码
随时随地手机看文章
[导读]今天给大家带来的是一道特别特别特别经典的题目接雨水问题，这个问题是很多算法书上面举例过的题目。虽然是难度题，但是相对来说还是比较容易理解的，代码长度也适中，说了这么多，就一个意思，大家记得打卡这个题目啊，真的是很nice的一道题，下面我们来看一下题目描述。
接雨水
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
示例3：
输入：[4,3,2,0,1,1,5]
输出：13
说明：上面是由数组 [4,3,2,0,1,1,5]表示的高度图，在这种情况下，可以接 13个单位的雨水（见下图）。
题目解析：
题目代码：
class Solution {
public int
trap(int[] height) {
Stack stack = new Stack();
int water = 0;
//特殊情况
if(height.length < 3){
return 0;
}
for(int i = 0; i < height.length; i++){
while(!stack.isEmpty() && height[i] > height[stack.peek()])
//栈顶元素
int popnum = stack.pop();
//相同元素的情况例1，1
while(!stack.isEmpty()&&height[popnum] == height[stack.peek()]){
stack.pop();
}
//计算该层的水的单位
if(!stack.isEmpty()){
int temp = height[stack.peek()];//栈顶元素值
//高
int hig = Math.min(temp-height[popnum],height[i]-height[popnum]);
//宽
int wid = i-stack.peek()-1;
water += hig * wid;
}
}
//这里入栈的是索引
stack.push(i);
}
return water;
}
}
这个题解的图片太多了，整了挺久，因为怕浪费了这道经典题，所以画了很多图片进行说明，希望可以帮到大家。下周就是字符串啦，大家加油啊！
免责声明：本文内容由21ic获得授权后发布，版权归原作者所有，本平台仅提供信息存储服务。文章仅代表作者个人观点，不代表本平台立场，如有问题，请联系我们，谢谢！
下载文档
