C++ Stack-based solution inspired by largest histogram problem.


  • 4
    T

    C++ Stack-based solution inspired by largest histogram problem.

    class Solution {
    public:
        int trap(vector<int>& height) {
            stack<int> s;
            int N = height.size();
            if (N < 3) return 0;
            int area = 0;
            for ( int i = 0 ; i < N; ++i){
                while (!s.empty() && height[i] > height[ s.top() ] ){
                    int low_h = height[s.top()];
                    s.pop();
                    if (!s.empty()) {
                        int w = i - s.top() - 1;
                        int h = min(height[i], height[s.top()]) - low_h;
                        area += w*h;
                    }
                }
                s.push(i);
            }
            return area;
        }
    };

Log in to reply
 

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