Givennnon-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]
, return6
.
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 Marcosfor contributing this image!
最后黑体字的Thanks Marcos的意思是让我们放大我们的想象力,因为上图很容易误导我们的。如果只有上图的情况的话,我们可以很好用贪心法解决,但是,用贪心法是会出错的,因为如果我们计算当前最低点,然后往两边扩展找到两边递增的最高点,那么这个最高点很可能是局部最高点,答案就会出错。
有两个解题思路:
1 两边往中间搜索
2 由左往右搜索,跳跃式计算
如下面的分析图,会比较直观:
蓝色代表水,可以看见很多局部最高点都被水淹了。
这里计算面积不用一般几何书的方法,这里是两边往中间遍历,记录当前第二高点secHight,然后利用这个第二高点减去当前历经的柱子,剩下就装水容量了。
为什么是第二高点?因为两边比较,最高的点不用动,只移动第二高点。
第一个思路,按照上图的思想就能写出非常简洁的程序了,时间复杂度为O(n):
int trap(int A[], int n) {
int secHight = 0;
int left = 0;
int right = n-1;
int area = 0;
while (left < right){
if (A[left] < A[right]){
secHight = max(A[left], secHight);
area += secHight-A[left];//计算当前格的能装雨水的容量
left++;
} else {
secHight = max(A[right], secHight);
area += secHight-A[right];
right--;
}
}
return area;
}
第二个思路,这个思路不难,但是分情况太多,会搞的很复杂,所以有兴趣的挑战一下,不推荐使用。时间复杂度也是O(n),可以AC。
class Solution {
public:
int trap(int A[], int n) {
int area = 0;
int begin = 0;
while (begin < n-1 && A[begin] <= A[begin+1]) begin++;
while (begin < n)
area += calculate(A, begin, n);
return area;
}
//前跃思想
int calculate(int A[], int &begin, int n)
{
int lowest = -1;
int highest = -1;
int i = 0;
//找最低点;也可以不用找最低点;找最低点可以优化一个特殊情况:后面很长的降序序列
for (i = begin; i < n-1; i++)
if (A[i] < A[i+1])
{
lowest = i;
break;//注意:记得break掉
}
//处理到了结尾的情况
if (lowest == -1)
{
begin = n;
return 0;
}
//找比begin还高的高点
int tempHight = -1;
int tempMax = -1;
for (i = lowest+1; i < n; i++)
{
if (A[i] > A[begin])
{
highest = i;
break;
}
//存储当前找到的最高度
if (A[i] >= tempMax)
{
tempHight = i;
tempMax = A[i];
}
}
//搜索到最后,没有高于begin的
if (i == n && n-1 != highest)
{
if (tempMax <= A[n-1])
highest = n-1;
else highest = tempHight;
}
//计算宽度
int width = highest - begin - 1;
//计算高度
int hight = min(A[begin], A[highest]);
//计算中间格子
int blocks = 0;
for (i = begin+1; i < highest; i++)
blocks += min(A[i], hight);
//计算中间面积
int area = width*hight;
area -= blocks;
//重新定位下一个begin
begin = highest;
return area;
}
};
//2014-1-27 update
int trap(int A[], int n)
{
int h = 0;
int sum = 0;
for (int i = 0, j = n-1; i < j; )
{
if (A[i] < A[j])
{
h = max(h, A[i]);
sum += h-A[i];
i++;
}
else
{
h = max(h, A[j]);
sum += h-A[j];
j--;
}
}
return sum;
}
分享到:
相关推荐
Trapping Rain Water LeetCode 61 RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels...
42. 接雨水解题思路(动态规划)复杂度分析时间复杂度:O(N)空间复杂度:O(N)代码实现i++ { // 一次遍历,计算出两个数组的值i++ { // 下标
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
leetcode 1004 leetcode NEXT:42 Trapping Rain Water 刷题顺序 刷题内容总的来说包括数据结构、算法和技巧 按照tag分类别进行刷题,跳过like<200>like的题目 按Acceptance由高到低进行,每个tag所刷题目大于20...
我自己在新学erlang,在LeetCode OJ上找了题目练习,题目很适合新手... "three_sum.erl","trapping_rain_water.erl", "valid_palindrome.erl" 个人认为dungeon_game这个题目解题逻辑很体现erlang的函数式的思维逻辑
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
c++ c++_c++编程基础之leetcode题解第42题接雨水
力码解决方案 Leetcode是一个网站,人们——...├── Trapping Rain Water │ ├── Readme.md │ └── solution.js ├── Wildcard Matching │ ├── Readme.md │ └── solution.js ├── Valid Number │
leetcode 不会3D 捕集雨水系统 该 repo 包含复杂 3D 雨水收集系统的解决方案,该系统在 Leetcode Problem No. 407 和 Google Interview Round 中提出。 此外,它将“0”视为系统的排水。 (查看自述文件以获得详细...
lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary...
leetcode中文版
vs code LeetCode 插件
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
示例 1:输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水
100个leetCode详细解答
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...