Simple O(n) c++


  • 0
    L
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            heights.push_back(0);
            int len = heights.size();
            stack<int> s;
            int maxsum = 0;
            for(int i = 0; i<len; i++)
            {
                while(!s.empty()&&heights[s.top()]>heights[i])
                {
                    int t = s.top();
                    s.pop();
                    maxsum = max(maxsum,heights[t]*(i-(s.empty()?-1:s.top())-1));
                }
                s.push(i);
            }
            return maxsum;
        }
    };

Log in to reply
 

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