题解 | #接雨水问题#

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        stack<int> id; // 单调递减栈 stack
        int n = arr.size();
        long long res = 0;
        for (int i = 0; i < n; i ++ ) {
            while (!id.empty() && arr[id.top()] < arr[i])
            {
                int mid = id.top(); // 取出夹起来的区间中点
                id.pop();
                if (id.empty()) break;    // 如果夹不住就退出循环
                
                int l = id.top();    // 左端点
                int r = i;            // 右端点
                
                int h = min(arr[l], arr[r]) - arr[mid];    // 区间高度
                int w = r - l - 1;        // 区间长度
                res += (long long)w * h;    // 区间面积
                
            }
            id.push(i);
        }
        return res;
    }
};