84.柱状图中最大的矩形
有了之前单调栈的铺垫,这道题目就不难了。
Tips:这道题我用了自己想出来的解法,两遍单调栈,分别找到左边和右边比当前柱子矮的坐标,然后再for循环一遍计算出每个柱子所能延展出来的矩形面积即可。
我的题解:
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
// 两遍单调栈,分别找到左边和右边比当前柱子矮的坐标
// 然后再for循环一遍计算出每个柱子所能延展出来的矩形面积即可
stack<int> st;
vector<int> leftMin(heights.size(),-1);
vector<int> rightMin(heights.size(),heights.size());
for(int i=0; i<heights.size(); i++){
while(!st.empty() && heights[i] < heights[st.top()]){
rightMin[st.top()] = i;
st.pop();
}
if(st.empty() || heights[i] >= heights[st.top()]){
st.push(i);
}
}
stack<int>().swap(st);
for(int i=heights.size()-1; i>=0; i--){
while(!st.empty() && heights[i] < heights[st.top()]){
leftMin[st.top()] = i;
st.pop();
}
if(st.empty() || heights[i] >= heights[st.top()]){
st.push(i);
}
}
int result = 0;
for(int i = 0; i<heights.size(); i++){
int temp = heights[i] * (rightMin[i] - leftMin[i] - 1);
result = max(result,temp);
}
return result;
}
};
标签:矩形,int,top,heights,60,柱状图,st,Day,size From: https://www.cnblogs.com/GavinGYM/p/17166410.html