题解 | 接雨水问题

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    //单调栈，空间复杂度为On
    /*long long maxWater(vector<int>& arr) {
        // write code here
        stack<int> st;//存下标，单调递减栈
        long long water=0;
        int n=arr.size();
        if(n<3)
        {
            return 0;
        }
        for(int i=0;i<n;i++)
        {
            while(!st.empty()&&arr[i]>arr[st.top()])//当栈中存在元素并且当前元素大于栈顶元素，所以说明此时有一个凹槽
            {
                //栈顶元素为坑底，弹出以后如果有栈顶则新的栈顶元素为左边界，当前元素为右边界；否则直接跳出
                int bottom=st.top();
                st.pop();
                if(st.empty())
                {
                    break;
                }
                int left=st.top();
                int minheight=min(arr[left],arr[i]);
                water+=((minheight-arr[bottom])*(i-left-1));
            }
            st.push(i);
        }
        return water;

    }*/
    //双指针，空间复杂度为O1
    //双指针的思路是左右两个指针往中间偏移，记录左指针左边最大的数组值和右指针右边最大的数组值
    //当遇到凹槽时当前指针的leftmax和rightmax都大于当前指针的数组值，此时只需计算当前数组值能装多少雨水
    //想象一下，左右两边都比该数组值高，所以当前数组值能存的雨水一定不会漏出,依次类推，统计每个比左右边界小的数组值
    //能装雨水，累加即可。
     long long maxWater(vector<int>& arr) {
        // write code here
        long long water=0;
        int n=arr.size();
        if(n<3)
        {
            return 0;
        }
        int left=0;
        int right=n-1;
        int leftmax=0;//left左边的最大值
        int rightmax=0;//right右边的最大值
        while(left<=right)//left可能和right在同一位置，例如遇到左边最高值，left是指向下一个，而right是指向右边最高值的上一个
        {
            if(leftmax<=rightmax)//左边界小，要以左边界为高计算雨水
            {
                if(arr[left]>leftmax)
                {
                    leftmax=arr[left];//更新左边界，确保左边界一定比当前数组值大，如果小，则不计算雨水
                }
                else 
                {
                    water+=(leftmax-arr[left]);//相当于只接当前位置所能装的雨水，即左边界与当前位置数组值的差值
                }
                left++;//右移，也能保证当前位置所装雨水值不会被累加计算
            }
            else //右边界小，要以右边界为高计算雨水
            {
              if(arr[right]>rightmax)
                {
                    rightmax=arr[right];//更新右边界，确保右边界一定比当前数组值大，如果小，则不计算雨水
                }
                else 
                {
                    water+=(rightmax-arr[right]);//相当于只接当前位置所能装的雨水，即右边界与当前位置数组值的差值
                }
                right--;//左移，也能保证当前位置所装雨水值不会被累加计算
            }
        }
       
        return water;

    }

};