leetCode 42.Trapping Rain Water(凹槽的雨水) 解题思路和方法
Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
思路:此题咋一看简单,可是细细思考。越想越复杂,感觉无从下手,无奈想了一天没搞定,仅仅能求助网上资料。最终思路例如以下:(网友非常强大)
(參考网址:http://www.xuebuyuan.com/1586534.html)
最后黑体字的Thanks Marcos的意思是让我们放大我们的想象力。由于上图非常easy误导我们的。假设仅仅有上图的情况的话,我们能够非常好用贪心法解决,可是。用贪心法是会出错的,由于假设我们计算当前最低点,然后往两边扩展找到两边递增的最高点,那么这个最高点非常可能是局部最高点,答案就会出错。
有两个解题思路:
1 两边往中间搜索
2 由左往右搜索,跳跃式计算
如以下的分析图,会比較直观:
蓝色代表水,能够看见非常多局部最高点都被水淹了。
这里计算面积不用一般几何书的方法,这里是两边往中间遍历,记录当前第二高点secHight,然后利用这个第二高点减去当前历经的柱子。剩下就装水容量了。
为什么是第二高点?由于两边比較。最高的点不用动,仅仅移动第二高点。
第一个思路,依照上图的思想就能写出很简洁的程序了,时间复杂度为O(n):
本人照着上面的思路写的代码例如以下:
public class Solution {
public int trap(int[] height) {
Stack<Integer> st = new Stack<Integer>();
if(height.length == 0)
return 0;
int i = 0;
int j = height.length - 1;
int ans = 0;//返回的答案
int secHight = 0;//第二个高度(最高的那个不动)
while(i < j){
if(height[i] < height[j]){
secHight = Math.max(secHight,height[i]);
//由于长度为1,高度也就是面积值。假设height[i]==secHight,则新增面积为0
ans += secHight - height[i];
i++;
}else{
secHight = Math.max(secHight,height[j]);
//由于长度为1,高度也就是面积值。假设height[i]==secHight,则新增面积为0
ans += secHight - height[j];
j--;
}
}
return ans;
}
}
最新文章
- Vue.js入门
- 动态计算Label高度
- Liferay 6.2 改造系列之十一:默认关闭CDN动态资源
- Android pix转换为sp
- ubuntu wubi安装注意事项
- C++赋值函数详解
- [ACM] hdu 1251 统计难题 (字典树)
- JAVA--可变长参数
- go实例之函数
- 1062 Text Reverse
- 如何使用Visual Studio Code开发Django项目
- MIUI通过xposed自动设置root权限
- scala-创建泛型数组(T: Manifest)
- PaddlePaddle Perceptron Example
- tesseract-ocr识别中文扫描图片实例讲解
- Tomcat 发布项目 conf/Catalina/localhost 配置 及数据源配置
- Delphi XE8中的DBExpress使用ODBC方式连接MySQL 5.6.24 X64!!!!
- Go语言基础之19--web编程基础
- (转)Java并发编程:阻塞队列
- java的大小端和转换