leetcode Trapping Rain Water

leetcode 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 Trapping Rain Water

题意：给定数组A，A[i]表示第i个位置的高度，求可以盛放雨水的容量。（参考图）

思路：

对于A[i],如果A[i]这个位置可以装水，那么左右两边必定各有一个数大于A[i], （设为left[i]和right[i]）且这个位置能放的量最多为min(left[i],right[i]) - A[i]

因此一个直接的想法就是维护两个数组，分别为左右两边的最大值：

C++

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left(n, 0), right(n, 0);
        for(int i = 1; i < n; ++i)
            left[i] = max(left[i - 1], height[i - 1]);
        for(int i = n - 2; i >= 0; --i)
            right[i] = max(right[i + 1], height[i + 1]);
        
        int ans = 0;
        for(int i = 1; i < n; ++i)
            ans += max(0, min(left[i], right[i]) - height[i]);
        return ans;
    }
};

另一种写法：

上面的写法left[i]是不包括当前i这个元素的，如果要包括，则可以写成下面这样：

但是最后的更新要改成min(left[i - 1],right[i + 1]) - A[i]

Java

class Solution {
    public int trap(int[] height) {
        final int n = height.length;
        if (n < 2) return 0;

        int[] maxLeft = new int[n];
        int[] maxRight = new int[n];
        maxLeft[0] = height[0];
        maxRight[n - 1] = height[n - 1];

        for (int i = 1; i < n; i++) 
            maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
        for (int i = n - 2; i >= 0; i--) 
            maxRight[i] = Math.max(maxRight[i + 1], height[i]);

        int ans = 0;
        for (int i = 1; i < n - 1; i++)
            ans += Math.max(0, Math.min(maxLeft[i - 1], maxRight[i + 1]) - height[i]);
        return ans;
    }
}

但能用双指针做得更好：

两个指针L=0 和 R =n-1，维护左边最大max_left和右边最大值max_right，如果 A[L] < A[R] 那么，那么若max_left > A[L]，那么A[L]这个位置可以装水，因为右边A[R]>A[L]，并且左边有元素也比较大，所以能装的水为max_left - A[L]，然后L++

A[L] > A[R]同理，是和A[R]进行比较，更新ans，然后R--

那么A[L] = A[R]的情况呢？任意的归为上面两种情况均可。这里假设归为第一种情况。那么max_left>A[L]，但是右边的A[L] = A[R]一定能装水么？答案是肯定的。假如不能装水，说明大于L的范围中，均有A[i] <= A[L]（i = L+1...n），但是max_left > A[L], 就是说不可能进入这个分支中。而如果进入了这个分支，那么说明此时R右边必然有比当时max_left来得大的元素。

C++

class Solution {
public:
    int trap(vector<int>& height) {
        int L = 0,R = height.size() - 1;
        int max_left = 0,max_right = 0,ans = 0;
        while(L < R){
            if(height[L] <= height[R]){
                max_left = max(max_left, height[L]);
                ans += max_left - height[L++];
            }
            else{
                max_right = max(max_right, height[R]);
                ans += max_right - height[R--];
            }
        }
        return ans;
    }
};

python

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_left = max_right = ans = 0
        L, R = 0, len(height) - 1
        while L < R:
            if height[L] <= height[R]:
                max_left = max(max_left, height[L])
                ans += max_left - height[L]
                L += 1
            else:
                max_right = max(max_right, height[R])
                ans += max_right - height[R]
                R -= 1
        return ans

另一种写法：

left和right为当前的元素位置，维护left_max和right_max分别代表left左边最大值和right右边的最大值。

若left_max < right_max，则说明left只能装left_max - height[left]了（当然需要left_max > height[left]），并让left +=1

否则，说明right只能装right_max - height[right]了（也需要right_max > height[right]），然后right-=1

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1, left_max = 0, right_max = 0;
        int ans = 0;
        while(left <= right){
            if(left_max < right_max){
                if(left_max > height[left])
                    ans += left_max - height[left];
                else
                    left_max = height[left];
                ++left;
            }
            else{
                if(right_max > height[right])
                    ans += right_max - height[right];
                else
                    right_max = height[right];
                --right;
            }
        }
        return ans;
    }
};

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/