CL 42. Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<pair<int, int>> st;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (st.size() == 0 || st.back().first > height[i]) {
                st.push_back({height[i], i});
                continue;
            }
            int lastHeight = st.back().first;
            while (st.size() > 0 && st.back().first <= height[i]) {
                st.pop_back();
                if (st.size() == 0) continue;
                auto [preHeight, preIndex] = st.back();
                int distance = i - preIndex - 1;
                int hei = min(preHeight, height[i]) - lastHeight;
                ans += distance * hei;
                lastHeight = preHeight;
            }
            st.push_back({height[i], i});
        }
        return ans;
    }
};

Time Complexity: O(n)
Space: O(n)

使用嚴格遞減的單調棧來計算出答案，我們在每次要 pop 最後的高度時計算一下可以注入的水量，基本公式為找到兩端中比較小的高度作為上限高度 min(preHeight, height[i]) ，再來就是計算出寬度 i - preIndex - 1 ，最後是計算最終添加的水高，會是 (上限高度 - lastHeight) ， 這樣就可以計算出移除最後的 st 時會增加多少水量。