84. 柱状图中最大的矩形
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n=heights.size();
if(n==0)return 0;
vector<int>newheight(n+2,0);
for(int i=1;i<=n;i++){
newheight[i]=heights[i-1];
}
heights=newheight;
n=heights.size();
stack<int>stk;
stk.push(0);
int res=0;
for(int i=1;i<n;i++){
while(heights[stk.top()]>heights[i]){
int h=heights[stk.top()];
stk.pop();
int w=i-stk.top()-1;
res=max(res,w*h);
}
stk.push(i);
}
return res;
}
};
单调栈练习
