Leetcode 42.接雨水

题目

朴素解法：

对于每列分别向左右扫描查找左右最高的柱子，对于每一个柱子接的水，那么它能接的水=min(左右两边最高柱子）-当前柱子高度。遍历每列时间复杂度为O(n)，每列再扫描O(n)，总共O(N^2)。

class Solution {
public:
    int trap(vector<int>& height) {
        //O(n^2)还是超时
        int ans=0;
        //按列求，只看每列能接多少水——找该列左右最高的柱子——短板效应
        for(int i=1;i<height.size();i++){
            int left = 0,right = 0;
            for(int j=0;j<i;j++)left = max(left,height[j]);
            for(int j=i+1;j<height.size();j++)right = max(right,height[j]);
            int temp = min(left,right);
            if(height[i] < temp)ans += temp-height[i];
        }
        return ans;
    }
};

动态规划：

每列都向左右扫描重复信息没有利用，考虑动态规划，用leftMax和rightMax数组记录每列的左右柱子最高高度。

• 从左向右扫描得到leftMax：leftMax[i] = max(leftMax[i-1],height[i])
• 从右向左扫描得到rightMax：rightMax[i] = max(rightMax[i-1],height[i])

双指针：

(实际是四指针但优化为了双指针)
动态规划中维护两个数组占用O（N）的空间，由于数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。

维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，
初始时 left=0,right=n−1,leftMax=0,rightMax=0。指针 left 只会向右移动，指针 right 只会向左移动，在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。

假设两柱子分别为 i，j。那么就有 iLeftMax,iRightMax,jLeftMx,jRightMax 这个变量。由于 j>i ，故 jLeftMax>=iLeftMax，iRigthMax>=jRightMax.

- 如果 iLeftMax>jRightMax，则必有 jLeftMax >= jRightMax，所以我们能接 j 点的水。
- 如果 jRightMax>iLeftMax，则必有 iRightMax >= iLeftMax，所以我们能接 i 点的水。

而上面我们实际上只用到了 iLeftMax，jRightMax 两个变量，故我们维护这两个即可。

代码

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

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 的长度。两个指针的移动总次数不超过 n。

空间复杂度：O(1)。只需要使用常数的额外空间。