LeetCode 84. 柱状图中最大的矩形
原题链接
困难
作者:
linux_2019
,
2019-09-05 09:01:57
,
所有人可见
,
阅读 824
C++ 代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<pair<int,int>> st;
heights.push_back(0);
vector<int> w(heights.size(),0);
st.push(make_pair(heights[0],1));
int ans=0;
for(int i=1;i<heights.size();i++)
{
if(st.top().first<heights[i])
{
st.push(make_pair(heights[i],1));
}
else
{
int width=0;
while(!st.empty()&&st.top().first>heights[i])
{
width+=st.top().second;
ans=max(ans,st.top().first*width);
st.pop();
}
st.push(make_pair(heights[i],width+1));
}
}
return ans;
}
};
有题解就更好了