Niuke.com: the double pointer problem of receiving rainwater

1. The container with the most water

The idea is as follows ：

Set two pointers , From both sides to the middle , Each move height Smaller end .

The code is as follows ：

class Solution {
public:
    /**
     *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly 
     *
     * 
     * @param height int integer vector 
     * @return int integer 
     */
    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. The rain problem

 

Double pointer

  This question is not much different from the one above . First, let's give an interval , We need to know , The amount of water corresponding to each value in this interval is determined by the smaller of the left and right boundaries .

therefore , We maintain a maxL and maxR Record the maximum value of the left and right intervals , Used to calculate water volume , And the process of computing is that we maintain a [left, right] Double pointer , From both sides to the middle , Move small at a time , Because in this way, we can calculate the maximum water receiving capacity , The middle height may be higher .

The code is as follows ：

class Solution {
public:
    /**
     * max water
     * @param arr int integer vector the array
     * @return long Long integer 
     */
    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;
    }
};

Monotonic stack

This problem is also suitable for solving with monotone stack , A monotone stack is a stack that maintains a monotone sequence , Here we maintain a decreasing subscript stack .

Here, the monotone stack simulates the process of adding water layer by layer for an interval . For details, please refer to leetcode The above ideas ：

Power button

The code is as follows ：

class Solution {
public:
    /**
     * max water
     * @param arr int integer vector the array
     * @return long Long integer 
     */
    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();
                // It means that the previous ones are younger than him   The corresponding position at this height cannot hold water 
                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;
    }
};