leetcode 84. 柱状图中最大的矩形

冷不防 2023-07-06 08:50 42阅读 0赞

思路： 单调栈

维护一个单调上升的栈。因为保证单调上升以后，从后面开始，每一个都可以作为高。为了方便计算宽度。先压入一个-1即可。

宽度计算的原理：取当前栈顶的元素，在当前栈顶之前的元素都比它小，所以，只要计算栈顶元素，与下一个栈顶元素直接的距离，就是宽了。

  1. class Solution {
  2. public:
  3.     int largestRectangleArea(vector<int>& heights) {
  4.         int n=heights.size();
  5.         stack<int> sta;
  6.         sta.push(-1);
  7.         int ans=0;
  8.         for(int i=0;i<n;i++)
  9.         {
  10.             while(sta.top()!=-1&&heights[sta.top()]>heights[i])
  11.             {
  12.                 int tmp=sta.top();
  13.                 sta.pop();
  14.                 ans=max(ans,heights[tmp]*(i-sta.top()-1));
  15.             }
  16.             sta.push(i);
  17.         }
  18.          while(sta.top()!=-1)
  19.         {
  20.             int tmp=sta.top();
  21.             sta.pop();
  22.             ans=max(ans,heights[tmp]*(n-sta.top()-1));
  23.         }
  26.         return ans;
  27.     }
  28. };

发表评论

表情：
评论列表 （有 0 条评论，42人围观）

还没有评论，来说两句吧...

相关阅读