The Double Pointer Problem (Part 2)

一、 盛水最多的容器

解法:贪心算法

这道题利用了水桶的短板原理,较短的一边控制最大水量,因此直接用较短边长乘底部两边距离就可以得到当前情况下的容积.但是要怎么找最大值呢？

可以利用贪心思想：我们都知道容积与最短边长和底边长有关,与长的底边一定以首尾为边,但是首尾不一定够高,中间可能会出现更高但是底边更短的情况,因此我们可以使用对撞双指针向中间靠,这样底边长会缩短,因此还想要有更大容积只能是增加最短变长,此时我们每次指针移动就移动较短的一边,因为贪心思想下较长的一边比较短的一边更可能出现更大容积.

//优先舍弃较短的边
if(height[left] < height[right]) 
    left++;
else
    right--;

• 优先排除不能形成容器的特殊情况.
• 初始化双指针指向数组首尾,每次利用上述公式计算当前的容积,维护一个最大容积作为返回值.
• 对撞双指针向中间靠,但是依据贪心思想,每次指向较短边的指针向中间靠,另一指针不变.
  

class Solution {
    
public:
    int maxArea(vector<int>& height) {
    
        //Exclude the case where the container cannot be formed
        if(height.size() < 2) 
            return 0;
        int res = 0; 
        //双指针左右界
        int left = 0; 
        int right = height.size() - 1;
        //共同遍历完所有的数组
        while(left < right){
     
            //计算区域水容量
            int capacity = min(height[left], height[right]) * (right - left);
            //维护最大值 
            res = max(res, capacity); 
            //优先舍弃较短的边
            if(height[left] < height[right]) 
                left++;
            else
                right--;
         }
        return res;
    }
};

时间复杂度：O(n),The two pointers together traverse the array once
空间复杂度：O(1),常数级变量,没有额外辅助空间

二、接雨水问题

解法:双指针

我们都知道水桶的短板问题,控制水桶水量的是最短的一条板子.这道题也是类似,我们可以将整个图看成一个水桶,两边就是水桶的板,中间比较低的部分就是水桶的底,由较短的边控制水桶的最高水量.但是水桶中可能出现更高的边,比如上图第四列,它比水桶边还要高,那这种情况下它是不是将一个水桶分割成了两个水桶,而中间的那条边就是两个水桶的边.

有了这个思想,解决这道题就容易了,因为我们这里的水桶有两个边,因此可以考虑使用对撞双指针往中间靠.

• 检查数组是否为空的特殊情况
• 准备双指针,分别指向数组首尾元素,代表最初的两个边界
• 指针往中间遍历,遇到更低柱子就是底,用较短的边界减去底就是这一列的接水量,遇到更高的柱子就是新的边界,更新边界大小.

class Solution {
    
public:
    long long maxWater(vector<int>& arr) {
    
        //排除空数组
        if(arr.size() == 0) 
            return 0;
        long long res = 0;
        //左右双指针
        int left = 0; 
        int right = arr.size() - 1; 
        //中间区域的边界高度
        int maxL = 0; 
        int maxR = 0;
        //直到左右指针相遇
        while(left < right){
     
            //每次维护往中间的最大边界
            maxL = max(maxL, arr[left]); 
            maxR = max(maxR, arr[right]);
            //较短的边界确定该格子的水量
            if(maxR > maxL) 
                res += maxL - arr[left++]; 
            else
                res += maxR - arr[right--];
        }
        return res;
    }
};

时间复杂度：O(n),The two pointers together traverse the entire array at most
空间复杂度：O(1),常数个变量,没有额外的辅助空间