[LeetCode] Trapping Rain Water-阿里云开发者社区

[LeetCode] Trapping Rain Water

2015-07-14 1047

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Note: The following idea is in fact from the last answer in this link, which leads to a clean code. I just reorganize it and add some explanations.

Note: The following idea is in fact from the last answer in this link, which leads to a clean code. I just reorganize it and add some explanations. I hope it is Ok.

The following are four solutions in C/C++/Java/Python respectively. The basic idea is that we set two pointers l and r to the left and right end of height. Then we get the minimum height (minHeight) of these pointers (similar to Container with Most Water due to the Leaking Bucket Effect) since the level of the water cannot be higher than it. Then we move the two pointers towards the center. If the coming level is less than minHeight, then it will hold some water. Fill the water until we meet some "barrier" (with height larger than minHeight) and update l and r to repeat this process in a new interval.

 1 int trap(int* height, int heightSize) {
 2     int l = 0, r = heightSize - 1, water = 0, minHeight = 0;
 3     while (l < r) { 
 4         while (l < r && height[l] <= minHeight)
 5             water += minHeight - height[l++];
 6         while (r > l && height[r] <= minHeight)
 7             water += minHeight - height[r--];
 8         minHeight = height[l] <= height[r] ? height[l] : height[r];
 9     }
10     return water;
11 }

C++

 1 class Solution {
 2 public:
 3     int trap(vector<int>& height) {
 4         int n = height.size(), l = 0, r = n - 1, water = 0, minHeight = 0;
 5         while (l < r) {
 6             while (l < r && height[l] <= minHeight)
 7                 water += minHeight - height[l++];
 8             while (r > l && height[r] <= minHeight) 
 9                 water += minHeight - height[r--];
10             minHeight = min(height[l], height[r]);
11         }
12         return water;
13     }
14 };

Java

public class Solution {
    public int trap(int[] height) {
        int n = height.length, l = 0, r = n - 1, water = 0, minHeight = 0;
        while (l < r) {
            while (l < r && height[l] <= minHeight)
                water += minHeight - height[l++];
            while (r > l && height[r] <= minHeight)
                water += minHeight - height[r--];
            minHeight = Math.min(height[l], height[r]);
        }
        return water;
    }
}

Python

 1 class Solution:
 2     # @param {integer[]} height
 3     # @return {integer} 
 4     def trap(self, height):
 5         n = len(height)
 6         l, r, water, minHeight = 0, n - 1, 0, 0
 7         while l < r:
 8             while l < r and height[l] <= minHeight:
 9                 water += minHeight - height[l]
10                 l += 1
11             while r > l and height[r] <= minHeight:
12                 water += minHeight - height[r]
13                 r -= 1
14             minHeight = min(height[l], height[r])
15         return water

[LeetCode] Trapping Rain Water

热门文章

最新文章

相关电子书