LeetCode 42. 接雨水

LeetCode 42. 接雨水

解法一

求每一列的水，我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。时间复杂度O(n^2)，超时

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        for (int i = 1;i < height.size()-1;i++) {
            int max_left = 0;
            for (int j = i - 1;j >= 0;j--) {
                max_left = max(max_left,height[j]);
            }
            int max_right = 0;
            for (int j = i+1;j < height.size();j++) {
                max_right = max(max_right,height[j]);
            }
            int min_num = min(max_left,max_right);

            if (min_num > height[i]) {
                ans += (min_num-height[i]);
            }
        }
        return ans;
    }
};

解法二

动态规划

首先用两个数组，max_left [i]代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。（一定要注意下，第 i 列左（右）边最高的墙，是不包括自身的，和力扣上边的讲的有些不同）

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

解法三

双指针

max_left [ i ] 和 max_right [ i ] 数组中的元素我们其实只用一次，然后就再也不会用到了。所以我们可以不用数组，只用一个元素就行了。我们先改造下 max_left。

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

未完待续...