Description

Submission

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.empty()) return 0;
        if(heights.size() == 1) return heights[0];
        stack<int> pStack;
        stack<int> hStack;
        int maxArea = 0;
        pStack.push(0);
        hStack.push(heights[0]);
        for(int i = 1; i < heights.size(); ++i) {
            if(heights[i] > hStack.top()) {
                hStack.push(heights[i]);
                pStack.push(i);
            }

            if(heights[i] < hStack.top()) {
                int last_p = i;
                while(!hStack.empty() && heights[i] < hStack.top()) {
                    int area = hStack.top() * (i - pStack.top());
                    if(area > maxArea) maxArea = area;
                    hStack.pop();
                    last_p = pStack.top();
                    pStack.pop();
                }
                hStack.push(heights[i]);
                pStack.push(last_p);
            }
        }
        while(!hStack.empty()) {
            int area = hStack.top() * (heights.size() - pStack.top());
            if(area > maxArea) maxArea = area;
            pStack.pop();
            hStack.pop();
        }
        return maxArea;
    }
};

References

1. https://kickstart.best/largest-rectangle/