84. Largest Rectangle in Histogram - cocoder39/coco39_LC GitHub Wiki

int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        int area = 0;
        
        heights.push_back(-1);
        for (int i = 0; i < heights.size(); i++) {
            while (! s.empty() && heights[i] <= heights[s.top()]) {
                int height = heights[s.top()];
                s.pop();
                int width = i - (s.empty() ? -1 : s.top()) - 1;
                area = max(area, height * width);
            }
            s.push(i);
        }
        heights.pop_back();
        return area;
    }