No.42 Trapping Rain Water

 1 class Solution
 2 {
 3 public:
 4     int trap(vector<int> &height)
 5     {/*
 6         雨水覆盖问题:
 7         每一个bar能承受的水量为:它左侧所有中最高的和右侧所有中最高的中取最小值作为一个瓶颈[否则也留不住],
 8                                  若该值大于当前bar的高度,其差值即为所求
 9         累加所有bar能承受的水量即为所求
10     法三:【左右两个指针】
11         找到最高的位置,将数组分为两部分:
12         对左侧数据,因为右边已经有了最高值,所以,类似法一,找到其左侧最高值[为瓶颈],再与当前bar的高度比较,若低于瓶颈,累加其差值;
13     对右侧数据,因为左边已经有了最高值,所以,找到右侧最高值[为瓶颈],再与当前bar的高度比较,若低于瓶颈,累加其差值
14     时间复杂度:O(n); 空间复杂度:O(1)
15      */
16         int count = height.size();
17         int res=0;
18         if(count < 3)//一个符号引发的错误,不是<=
19             return 0;
20         
21         int l = 0;
22         int r = count-1;
23         int min;
24         while(l<r)
25         {
26             min = (height[l]<=height[r] ? height[l] : height[r]);
27             if(height[l] == min)
28             {
29                 l++;
30                 while(l<r && height[l]<min)
31                 {
32                     res += min-height[l];
33                     l++;
34                 }
35             }
36             else
37             {
38                 r--;
39                 while(l<r && height[r] < min)
40                 {
41                     res += min-height[r];
42                     r--;
43                 }
44             }
45 
46         }
47         return res;
48     }
49 };

 

No.42 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.

技术分享

Tags: Array Stack Two Pointers

 

每一个bar能承受的水量为:它左侧所有中最高的和右侧所有中最高的中取最小值作为一个瓶颈[否则也留不住],
                   若该值大于当前bar的高度,其差值即为所求
累加所有bar能承受的水量即为所求

思路清晰,一切不是问题

 

方法一:从左向右扫描,找到当前bar左侧最高的记录下来;

    从右向左扫描,找到当前bar右侧最高的,将其与左侧最高比较,取其小作为瓶颈

    若当前bar的高度低于瓶颈,差值累加得到结果

    时间复杂度:O(n); 空间复杂度:O(n)

 1 #include "stdafx.h"
 2 #include <vector>
 3 #include <iostream>
 4 using namespace std;
 5 
 6 class Solution
 7 {
 8 public:
 9     int trap(vector<int> &height)
10     {/*
11         雨水覆盖问题:
12         每一个bar能承受的水量为:它左侧所有中最高的和右侧所有中最高的中取最小值作为一个瓶颈[否则也留不住],
13                                  若该值大于当前bar的高度,其差值即为所求
14         累加所有bar能承受的水量即为所求
15      */
16         int count = height.size();
17         int res=0;
18         if(count < 3)//一个符号引发的错误,不是<=
19             return 0;
20         int *container = new int[count];//辅助数组
21         int max=0;//记录当前出现的最大值
22         for(int i=0; i<count; i++)
23         {//计算i左侧的最大值
24             container[i] = max;
25             max = (height[i]>max ? height[i] : max);//更新max
26         }
27         max = 0;
28         for(int i=count-1; i>=0; i--)
29         {//计算i右侧的最大值
30             container[i] = (max<container[i] ? max : container[i]);
31             max = (height[i]>max ? height[i] : max);//更新max
32             //同时统计总容量
33             res += (container[i]>height[i] ? (container[i]-height[i]) : 0 );
34         }
35         delete[] container;//别忘
36         return res;
37     }
38 };
39 
40 int main()
41 {
42     Solution sol;
43 //    int data[] = {0,1,0,2,1,0,1,3,2,1,2,};
44     int data[] = {2,0,2};
45     vector<int> test(data,data+sizeof(data)/sizeof(int));
46 
47     cout << sol.trap(test)<<endl;
48 
49 }

 

方法二:找到最高的位置,将数组分为两部分:

    对左侧数据,因为右边已经有了最高值,所以,类似法一,找到其左侧最高值【为瓶颈】(肯定小于右侧最高点),再与当前bar的高度比较,若低于瓶颈,累加其差值;

    对右侧数据,因为左边已经有了最高值,所以,找到右侧最高值【作为瓶颈】,再与当前bar的高度比较,若低于瓶颈,累加其差值

    时间复杂度:O(n); 空间复杂度:O(1)

 1 class Solution
 2 {
 3 public:
 4     int trap(vector<int> &height)
 5     {/*
 6         雨水覆盖问题:
 7         每一个bar能承受的水量为:它左侧所有中最高的和右侧所有中最高的中取最小值作为一个瓶颈[否则也留不住],
 8                                  若该值大于当前bar的高度,其差值即为所求
 9         累加所有bar能承受的水量即为所求
10     法三:【左右两个指针】
11         找到最高的位置,将数组分为两部分:
12         对左侧数据,因为右边已经有了最高值,所以,类似法一,找到其左侧最高值[为瓶颈],再与当前bar的高度比较,若低于瓶颈,累加其差值;
13     对右侧数据,因为左边已经有了最高值,所以,找到右侧最高值[为瓶颈],再与当前bar的高度比较,若低于瓶颈,累加其差值
14     时间复杂度:O(n); 空间复杂度:O(1)
15      */
16         int count = height.size();
17         int res=0;
18         if(count < 3)//一个符号引发的错误,不是<=
19             return 0;
20         
21         int maxIndex = 0;
22         //找到最高点的位置,将数组一分为二
23         for(int i=0 ; i<count; i++)
24         {
25             if(height[i] > height[maxIndex])
26                 maxIndex = i;
27         }
28         int max=0;//记录左侧/右侧当前最大值
29         for(int i=0; i<maxIndex; i++)
30         {
31             res += ((height[i] < max ? max-height[i] : 0));//注意细节!!!
32             max = (height[i]>max ? height[i] : max );
33         }
34 
35         max = 0;
36         for(int i=count-1; i>maxIndex; i--)
37         {
38             res += ((height[i] < max ? max - height[i] : 0));
39             max = (height[i]>max ? height[i] : max );
40         }
41         return res;
42     }
43 };

 

法三: 两指针法【理解上,还是有点问题】

  用两个指针从两端往中间扫瞄,

  在当前窗口下:

    如果哪一侧的高度是小的,那么从这里开始继续扫;

    如果比它还小的,肯定装水的瓶颈就是它了,可以把装水量加入结果;

    如果遇到比它大的,立即停止,重新判断左右窗口的大小情况,重复上面的步骤。这里能作为停下来判断的窗口,说明肯定比前面的大了,所以目前肯定装不了水(不然前面会直接扫过去)。

    这样当左右窗口相遇时,就可以结束了,因为每个元素的装水量都已经记录过了。

 

 

参考:http://blog.csdn.net/linhuanmars/article/details/20888505

 

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。