网站数据库如何导入,网站推广服务公司,深圳外贸公司名单,如何制作app推广目录 84 柱状图中最大的矩形 84 柱状图中最大的矩形 找每个柱子左右两边第一个小于该柱子的柱子#xff0c;栈头到栈底的顺序应该从大到小 求解矩形面积需要分别得到该柱左边和右边高度小于本柱的柱子 class Solution {
public:int largestRectangleArea(vectorint栈头到栈底的顺序应该从大到小 求解矩形面积需要分别得到该柱左边和右边高度小于本柱的柱子 class Solution {
public:int largestRectangleArea(vectorint heights) {int res 0;stackintst;heights.insert(heights.begin(),0);heights.push_back(0);st.push(0);for(int i 1;i heights.size();i){if(heights[i] heights[st.top()]){st.push(i);}else{//此时新柱子的高度小于栈顶柱子作为栈顶柱子右边的柱子while(!st.empty() heights[i] heights[st.top()]){//确保单调栈从大到小int mid st.top();st.pop();int l st.top();//由单调递减栈的性质可知栈中存放的其他柱子的高度都比栈顶柱子底此柱子可以作为原栈顶柱子左边的柱子int r i;int w r - l - 1;//计算出宽度int h heights[mid];//新柱子的高度res max(res,h * w);}st.push(i);}}return res;}
};
时间复杂度O(n)
空间复杂度O(n)
