84. 柱状图中最大的矩形

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> sta;
        // 头部和尾加入0
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        sta.push(0);
        int res = 0;
        for (int i = 1; i < heights.size(); i ++)
        {
            while(heights[i] < heights[sta.top()])
            {
                int mid = sta.top();
                sta.pop();
                int w = i - sta.top() - 1;
                int h = heights[mid];
                res = max(res, w * h);
            }
            sta.push(i);
        }
        return res;
    }
};