84. Largest Rectangle in Histogram

84.cpp

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