柱状图中最大的矩形

题目链接：柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

方法一：单调栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        stack<int> s;
        int res = 0;
        for (int i = 0;i < heights.size();i++) {
            while (s.size() && heights[s.top()] > heights[i]) {
                int cur = s.top();
                s.pop();
                res = max(res,(i - 1 - s.top()) * heights[cur]);
            }
            s.push(i);
        }
        return res;
    }
};