O(n) clean solution with two stacks in C++


  • 0
    M
    1. hs stack stores height.
    2. ps stack stores the position from which that particular height rectangle can start.
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            int ans=0, temp1, temp2, len=heights.size();
            stack<int> hs,ps;
            for(int i=0;i<len;i++)
            {
                if(hs.empty() || hs.top() < heights[i])
                {
                    hs.push(heights[i]);
                    ps.push(i);
                }
                else if(hs.top() > heights[i])
                {
                    while(!hs.empty() && hs.top() > heights[i])
                    {
                        temp1=hs.top();
                        temp2=ps.top();
                        hs.pop();
                        ps.pop();
                        ans=max(ans, (i-temp2)*temp1);
                    }
                    hs.push(heights[i]);
                    ps.push(temp2);
                }
            }
            while(!hs.empty())
            {
                temp1=hs.top();
                temp2=ps.top();
                hs.pop();
                ps.pop();
                ans=max(ans, (len-temp2)*temp1);
            }
            return ans;
        }
    };

Log in to reply
 

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