给定 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;
}
};