题解 | #接雨水问题#

public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     从左侧维护一个左侧最高值 单调栈，从右侧开始遍历找到能存雨水的位置，找到后计算并更新右侧最高
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        stack<int> st;
        int n = arr.size();
        for(int i=0;i<n-1;i++){
            if(st.empty() || arr[i] > st.top()){
                st.push(arr[i]);
            }else{
                st.push(st.top());
            }
        }
        int r = arr[n-1];
        long long res = 0;
        for(int i=n-2;i>=1;i--){
            
            if(arr[i] < st.top() && arr[i] < r){
                res +=min(st.top(), r) - arr[i];  
            }
            if(arr[i] > r){
                r = arr[i];
            }
            st.pop();
        }
        return res;
    }
};