84. 柱状图中最大的矩形

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

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

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

首先单调栈 首先要确定左右的范围
因为画矩形时，要找到比heights【i】左右小的连个坐标 即为最大的范围
因此从栈底到栈顶 的顺序是从小到大

其次使用的元素是栈顶的元素 和 栈顶的下一个元素
因此需要在数组的前面添加一个0

> 单调栈

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) { 
        if(heights.size() == 1) return heights[0];
        stack<int> sta;
        sta.push(0);
        int sum = 0;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int len = heights.size();
        for(int i = 1;i < len;i++){
            int idx = sta.top();
            while(heights[idx] > heights[i]){
                sta.pop();
                if(!sta.empty()){
                    int w = i - sta.top() - 1;
                    int h = heights[idx];
                    sum = max(sum,w*h);
                    idx = sta.top();
                }
                else{
                    break;
                }
            }
            sta.push(i);
        }
        return sum;
    }
};