class Solution {
public:
int largestRectangleArea(vector<int>& h) {
vector<int> l=vector<int>(h.size());
vector<int> r=l;
stack<int> stk;
int res=0;
//初始化l和r数组,分别记录左右两边小于h[i]的下标
for(int i=0;i<h.size();i++)
{
while(stk.size()&&h[i]<=h[stk.top()])
stk.pop();
if(!stk.size()) l[i]=-1;//没有比它小的数
else l[i]=stk.top();
stk.push(i);
}
stk=stack<int> ();
for(int i=h.size()-1;i>=0;i--)
{
while(stk.size()&&h[i]<=h[stk.top()])
stk.pop();
if(!stk.size()) r[i]=h.size();//没有比它小的数
else r[i]=stk.top();
stk.push(i);
}
//枚举每个长度
for(int i=0;i<h.size();i++)
res=max(h[i]*(r[i]-l[i]-1),res);
return res;
}
};
84. 柱状图中最大的矩形
发布时间 2023-03-31 16:55:21作者: 穿过雾的阴霾