双向双指针应用最典型的就是接雨水问题。

Container With Most Water

You are given an integer array heightof length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and(i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

思路

1. 假设left和right组成容器，则容器的高度取决于短的一条线。
2. 假设短的那条线是right，容器内任何一条高度mid如果和right组成的新容器，容积必定小于原容器；而与left形成新容器的话，容积可能增大。
3. 故而求出当前容器容积后，可以抛弃right继续考虑其余情况。

代码如下：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n-1;
        int res = 0;
        while(left<right){
            int area = (right - left)*min(height[left],height[right]);
            res = max(res,area);
            if(height[right]>height[left]){
                left++;
            }else{
                right--;
            }
        }
        return res;
    }
};

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 can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) 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.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

方法一：前后缀分解

积水的总和就是每一个格子积水相加。我们观察例1里的第六格位置，可以发现，当前格子能够积水高度取决于左边边界和右边边界的最小值。

右边边界就是往右边看去的最大高度，这里就是3。左边的高度就是往左边看去的最大高度，之里就是2。当然最后的容积还要减去当前格子的底部高度height[i]。

所以我们可以保留前缀数组，计算每个格子的左边最大高度。保留一个后缀数组，记录每个格子右边的最大高度。

代码：

public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> pre_max(n);
        pre_max[0] = height[0];
        vector<int> suf_max(n);
        suf_max[n-1] = height[n-1];

        for(int i =1;i<n;++i){
            pre_max[i] = max(pre_max[i-1],height[i]);
        }
        for(int i = n-2;i>=0;--i){
            suf_max[i] = max(suf_max[i+1],height[i]);
        }

        int total_area = 0;
        for(int i = 0;i<n;++i){
            int area = min(pre_max[i],suf_max[i]) - height[i];
            total_area += area;
        }
        return total_area;
    }
};

复杂度分析

• 时间复杂度：\(O(n)\)，其中\( n\) 为 \(\textit{height}\)的长度。
• 空间复杂度：\(O(n)\)。

方法二：相向双指针

上述方法时间复杂度已经无法优化了，我们可以优化下空间复杂度。

我们不用记录前后缀数组，看看双指针相向运动时候会发生什么。假设运动到left和right处。我们知道：

• 当前格子的容积取决于左右最小高度
• 前后缀数组单调不减

那么假设这个时候pre[left]<suffix[right]，那么左边这个格子的容积可以确定了，因为这个格子的左边高度就是pre[left],右边高度必然不小于suffix[right]。

代码

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

复杂度分析

• 时间复杂度：\(O(n)\)，其中 \(n\) 为 \(\textit{height}\)的长度。
• 空间复杂度：\(O(1)\)，仅用到若干变量。