Super simple stack method

  • 0

    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] < {
                else {
                    int bottom =  height[];
                    if (!stk.empty())
                        ans += (min(height[i],height[])-bottom)*(;
                    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.