牛客网：接雨水的双指针问题

1.盛水最多的容器

思路如下所示：

设置两个指针，从两边向中间靠拢，每次移动height较小的一端。

代码如下所示：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param height int整型vector 
     * @return int整型
     */
    int maxArea(vector<int>& height) {
        // write code here
        if(height.size()<0){
            return 0;
        }
        int res=0;
        int left=0, right=height.size()-1;
        while(left<right){
            res=max(res, min(height[left], height[right])*(right-left));
            if(height[left]>height[right]){
                right--;
            }else{
                left++;
            }
        }
        return res;
    }
};

2.接雨水问题

 

双指针

 这题其实和上边那道差不太多。首先给定一个区间，我们要知道，决定这个区间每个值对应的水量是和左右边界谁小决定的。

因此，我们维护一个maxL和maxR记录包含左右区间的最大值，用于计算水量，而计算的过程是我们维护一个[left, right]的双指针，由两侧向中间靠拢，每次将小的移动，因为这样我们才能计算出最大的接水量，中间的高度可能更高。

代码如下所示：

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        if(arr.size()==0){
            return 0;
        }
        long long res=0;
        int left=0, right=arr.size()-1;
        int maxL=0, 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;
    }
};

单调栈

这题也很适合用单调栈来解决，单调栈即维护一个单调序列的栈，这里我们维护一个递减的下标栈。

这里单调栈模拟的是对于一个区间一层一层加水的过程。具体可以参考leetcode上面的思路：

力扣

代码如下所示：

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        if(arr.size()==0){
            return 0;
        }
        long long res=0;
        stack<int> st;
        for(int i=0;i<arr.size();++i){
            while(!st.empty() && arr[i]>arr[st.top()]){
                int top=st.top();
                st.pop();
                //说明之前的都比他小 这个高度的对应位置装不了水
                if(st.empty()){
                    break;
                }
                int left=st.top();
                int width=i-left-1;
                int height=min(arr[left], arr[i])-arr[top];
                res+=width*height;
            }
            st.push(i);
        }
        return res;
    }
};