leetcode problem 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.

技术分享

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!

 

 

思路:

  这一道题类似于leetcode 11 题Container With Most Water.  要求最多能装多少水.有两种思路.

  思路一:

    先从左往右遍历.每遍历一个数字,就贪心得到这个数字所在的格子能最多装水. 由于是从左到右遍历,我们只考虑的左边的高度,没有考虑右边的高度(实际应该选择两者小的那个). 因此需要再从右往左遍历,同样贪心这个数字所在格子

  最多能装多少水,这次以右边高度为准. 最终综合从左到右和从右到左的结果,取两者小的.

 

代码:(runtime 19ms)

技术分享
 1 class Solution {
 2 public:
 3     int trap(vector<int>& height) {
 4         vector<int> leftToRight;
 5         vector<int> rightToLeft;
 6         aux_function(height.begin(), height.end(), leftToRight);
 7         
 8         aux_function(height.rbegin(), height.rend(), rightToLeft);
 9 
10         int ans = 0;
11         auto it1 = leftToRight.begin();
12         auto it2 = rightToLeft.rbegin();
13 
14         while (it1 != leftToRight.end()){
15             ans += min(*it1++, *it2++);
16         }
17         return ans;
18     }
19 
20 private:
21 template<class Iter>
22     void aux_function(Iter begin, Iter end, vector<int> &ret) {
23         int left = 0;
24         for (auto it = begin; it != end; it++) {
25             left = left > *it ? left : *it;
26             ret.push_back(left - *it);
27         }
28     }
29 };
View Code

 

  思路二:

技术分享

    如上图中所示, 先求黑色格子与蓝色格子的总面积,然后再减去黑色各自面积.

代码:(runtime 10ms)

  

技术分享
class Solution {
public:
    int trap(vector<int> A) {
        int n = A.size();
        int summap = 0;
        int sumtot = 0;

        for(int i = 0; i < n; i++) summap += A[i];

        int left = 0, right = n - 1;
        int leftbar = 0, rightbar = 0;
        while(left <= right) {
            leftbar = max(A[left], leftbar);
            rightbar = max(A[right], rightbar);

            if(leftbar <= rightbar) {
                sumtot += leftbar;
                left++;
                //right--;
            } else {
                sumtot += rightbar;
                right--;
                //left++;
            }
        }

        return sumtot - summap;
    }
};
View Code

 

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