42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

class Solution {
public:
    int trap(vector<int>& height) {
        stack<pair<int, int>> st;
        int res = 0;
        st.push({0, 1});
        for(auto& h : height) {
            if(st.top().first < h) {
                unordered_map<int, int> m;
                int maxHeight = 0, count = 0;
                while(!st.empty() && maxHeight < h) {
                    m[st.top().first] += st.top().second;
                    maxHeight = max(maxHeight, st.top().first);
                    count += st.top().second;
                    st.pop();
                }
                if(maxHeight < h) {
                    st.push({h, 1});
                } else {
                    st.push({maxHeight, m[maxHeight]});
                    st.push({h, count - m[maxHeight] + 1});
                }
                int trapHeight = min(maxHeight, h);
                if(!trapHeight) continue;
                for(auto entity : m) {
                    if(entity.first >= trapHeight) continue;
                    res += (trapHeight - entity.first) * entity.second;
                }
            } else {
                st.push({h, 1});
            }
        }
        return res;
    }
};