Super simple stack method


  • 0
    A

    Using the same method as the max-rectangle problem. Use the stack top as the bottom, second stack top as the left boundary, current as the right boundary, then accumulate the total area.

       int trap(vector<int>& height) {
            stack<int> stk;
            int ans = 0;
            for (int i = 0; i < height.size(); ++i) {
                if (stk.empty() || height[i] < stk.top()) {
                    stk.push(i);
                }
                else {
                    int bottom =  height[stk.top()];
                    stk.pop();
                    if (!stk.empty())
                        ans += (min(height[i],height[stk.top()])-bottom)*(i-stk.top()-1);
                    i--; //stay at the same place for further merge
                }
            }
            return ans;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.