leetcode84柱状图中最大的矩形

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]  
思路：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 2]

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

stack<int> 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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20221005/a071232372f64152b401c55cd1561401.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 1]: /images/20221005/1f2806ff433849ad99c010fd9794f142.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70 2]: /images/20221005/12b11b15e562487fa8895df7bf9795ca.png