题解 | #接雨水问题#

单调栈法:

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        int len = arr.size();
        if(len <= 2) return 0;
        stack<int> st;
        st.push(0);
        long long sum = 0LL;
        for(int i = 1; i < len; ++i) {
            while(!st.empty() && arr[i] > arr[st.top()]) {
                int mid = st.top();
                st.pop();
                if(!st.empty()) {
                    long long h = min(arr[st.top()], arr[i]) - arr[mid]; // 这里一定要用long long
                    int w = i - st.top() - 1;
                    sum += h*w;
                } 
            }
            st.push(i);
        }
        return sum;
    }
};