leetcode84柱状图中最大的矩形-蒲公英云

leetcode84柱状图中最大的矩形

小灰灰 2022-10-06 06:52 290阅读 0赞

在这里插入图片描述

思路：

使用单调递增栈，横向的长度是找到当前柱子左边第一个比它小的，和右边第一个比它小的，长度是两个小柱子的中间位置
（1）如果新元素比栈顶元素大就入栈
（2）如果新元素比较小，就将栈内的元素一直弹出，直至栈顶比新元素小
每次遇到比栈顶小的元素时才更新，那么为了计算最后一个数字，将0压入栈。
单弹出时栈为空，说明该栈顶元素是[0,i]的最小元素，其面积为heights[s.top()]*i，其他时候则是left = 该栈顶元素最左边边界值并包括该边界值，right = 当前值的左边位置并包括该位置
（1）left = s.back()+1 ;right = i-1;weight=right-left+1

代码模板

stack st;
for(int i = 0; i < nums.size(); i++)
{

while(!st.empty() && st.top() > nums[i])
{ 
    st.pop();
    //left;
    //right;
}
st.push(nums[i]);

}

代码

int largestRectangleArea(vector<int>& heights) { 
  vector<int> s;
  int i;
  int res = 0;
  heights.push_back(0);
  for(i=0;i<heights.size();++i){ 
      while (!s.empty()&&heights[s.back()]>heights[i])
      { 
          int h = heights[s.back()];
          s.pop_back();
          if(s.empty()){ 
              res =max(res,i*h);
          }
          else { 
               res = max(res,(i-s.back()-1)*h);
          }    
      }
      s.push_back(i);
  }
  return res;
}