Mind palace

some thoughts

0%

42. Trapping Rain Water

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

O(n)
跟11. Container With Most Water方法几乎一样

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        l, r, res = 0, n - 1, 0
        while l < r:
            mn = min(height[l], height[r])
            while l < r and height[l] <= mn:
                res += mn - height[l]
                l += 1
            while l < r and height[r] <= mn:
                res += mn - height[r]
                r -= 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int l = 0, r = n - 1;
        int res = 0;
        while (l < r) {
            int mn = min(height[l], height[r]);
            while (l < r && height[l] <= mn) {
                res += mn - height[l];
                ++l;
            }
            while (l < r && height[r] <= mn) {
                res += mn - height[r];
                --r;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int trap(vector<int>& height) {
        int left(0), right(height.size() - 1), ret(0);
        while (left < right) {
            auto min(std::min(height[left], height[right]));
            if (min == height[left])
                while (++left < right && height[left] < min)
                    ret += min - height[left];
            else
                while (left < --right && height[right] < min)
                    ret += min - height[right];
        }
        return ret;
    }
};