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

1.盛水最多的容器

思路如下所示：

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

代码如下所示：

class Solution {
public:
    
    int maxArea(vector& height) {
        // write code here
        if(height.size()<0){
            return 0;
        }
        int res=0;
        int left=0, right=height.size()-1;
        while(leftheight[right]){
                right--;
            }else{
                left++;
            }
        }
        return res;
    }
};

2.接雨水问题

 

双指针

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

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

代码如下所示：

class Solution {
public:
    
    long long maxWater(vector& arr) {
        if(arr.size()==0){
            return 0;
        }
        long long res=0;
        int left=0, right=arr.size()-1;
        int maxL=0, maxR=0;
        while(leftmaxL){
                res += maxL-arr[left++];
            }else{
                res += maxR-arr[right--];
            }
        }
        return res;
    }
};

单调栈

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

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

力扣

代码如下所示：

class Solution {
public:
    
    long long maxWater(vector& arr) {
        if(arr.size()==0){
            return 0;
        }
        long long res=0;
        stack st;
        for(int i=0;iarr[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;
    }
};