题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10示例 2：
输入： heights = [2,4]
输出： 4提示：
1 <= heights.length <=105
0 <= heights[i] <= 104思路
遍历数组，以每一个高度向左右两边扩展形成的最大矩形，即是一个候选答案。
从所有候选答案中选择最大值就是答案。对于第i个高度，向左扩展，
找到第一个比i高度小的值，就停止，假设其下标为l。向右扩展，找到第一个比i高度小的值，
就停止,假设其下标为r。那么高度i所能形成的最大矩形面积就是 (r-l-1)*heights[i]。
比较所有的值，就可以找到最大值。怎么找l和r呢?看i-1的高度是否比i高度小，如果小，那就找到了l。
如果不小，则舍弃i-1，看i-2的值，是否比i高度小，如果小，那就找到了l。如果不小，则舍弃i-2,看i-3的值。
重复这个过程，直到找到为止。假设找到l为i-3，则i-1,i-2舍弃了。对于i+1，i-1,i-2还有用吗?如果i+1比
i大。则i+1的l就是i,如果i+1和i相等，i+1的l就是i的l，是i-3。如果i+1比i小，因为i-1,i-2都是大于等于i,
所以i-1,i-2也是大于i+1,所以i-1,i-2对于i+1的l不起作用了。基于以上讨论，用一个栈来存储i之前的高度，
规定从栈底到栈顶的高度依次减小，那么i的左侧l就是栈顶元素。同理可以找右侧的r。
代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n),right(n);
stack<int> stk;
for(int i = 0;i < n;i++) {
while(!stk.empty()&&heights[stk.top()]>=heights[i]) {
stk.pop();
}
left[i] = stk.empty()?-1:stk.top();
stk.push(i);
}
stk = stack<int>();
for(int i = n-1;i>=0;i--) {
while(!stk.empty()&&heights[stk.top()]>=heights[i]) {
stk.pop();
}
right[i] = stk.empty()?n:stk.top();
stk.push(i);
}
int ans = 0;
for(int i = 0;i < n;i++) {
ans = max(ans,heights[i]*(right[i]-left[i]-1));
}
return ans;
}
};