接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

按列来计算，第i列接到的雨水等于min(i左边最大高度，i右边最大高度)-height[i].

所以问题的关键就变成了求i左右两边的最大高度。这是一个非常简单的动态规划问题。

  • 定义left数组，left[i]表示i左边最大高度（包括i，如果i左边最大高度就是height[i],则第i列接不到雨水，右边同理）。初始化left[0]=height[0]

    left[i]=max(left[i-1],height[i])

  • 定义right数组，right[i]表示i右边最大高度。 初始化right[n-1]=height[n-1]

    right[i]=max(right[i+1],height[i])

注意： right数组必须从后往前遍历。第一次就写反了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        if(!n) return 0;
        vector<int> left(n);
        left[0]=height[0];
        for(int i=1;i<n;i++)
            left[i]=max(left[i-1],height[i]);
        vector<int> right(n);
        right[n-1]=height[n-1];
        for(int i=n-2;i>-1;i--)
            right[i]=max(right[i+1],height[i]);
        int ans=0;
        for(int i=0;i<n;i++)
            ans+=min(right[i],left[i])-height[i];
        return ans;
    }
};

时空复杂度均为O(n).

仔细看上边代码，会发现没有必要设置两个数组。因为对于left数组只会用到left[i-1]和left[i]，right同理。所以可以用双指针将空间复杂度优化到常数。

设置两个指针left和right初始时分别指向0和n-1，相向移动。两指针相遇时返回ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int trap(vector<int>& height) {
        int n=height.size();
        if(!n) return 0;
        int leftmax=0,rightmax=0;
        int left=0,right=n-1;
        int ans=0;
        while(left<right){
            leftmax=max(height[left],leftmax);
            rightmax=max(height[right],rightmax);
            if(leftmax<rightmax) ans+=leftmax-height[left++];
            else ans+=rightmax-height[right--];
        }
        return ans;
    }
};