LeetCode#84

LeetCode#84柱状图中最大的矩形

题目链接

单调栈顾名思义，是单调的栈
（这不废话吗），即栈内的所有元素都为单调递增或递减的。单调栈看似简单，但是在实际应用中可以通过O(n)的时间复杂度来完成很多复杂的遍历。

以这道题来说，看到题目后我第一想法是直接暴力遍历，挨个遍历每一个矩形，然后分别往左右进行扩展，找到相邻的所有高度大于当前矩形的矩形，进而求出大矩形的宽度，但是这样的时间复杂度会达到一个爆炸的状态（尤其数据比较恶心且数据量很大的时候），极有可能会t。

这时候就轮到单调栈来登场了，先放上我学习单调栈用到的链接，我们还是分别以每一个矩形的高度作为高，但是这次我们只需要遍历一次就可以得到所有高度的最大矩形。原文作者已经讲的很清晰了，我在此基础上再补充一些我在自己做这道题过程中的一点理解。

先附上自己写的代码：

class Solution {
public:
   int largestRectangleArea(vector<int>& heights) {
       heights.push_back(0);
       stack<int>sta;
       int maxnum = 0;
       for(int i = 0 ; i < heights.size() ; i++)
       {
           while(!sta.empty() && heights[i] < heights[sta.top()])
           {
               int top = sta.top();
               sta.pop();
               if(sta.empty())
                maxnum = max(maxnum,heights[top]*i);
               else
               maxnum = max(maxnum,heights[top] * (i - (sta.top() + 1)));
           }
           sta.push(i);
       }
       return maxnum;
    }
};

• 在计算宽度的时候为什么要区分每一个矩形的左右边沿？因为heights数组是从0开始的，且每一个矩形是有自身的宽度的，不能简单的看作一个点或者一条线，而在计算宽度的时候这些都是要考虑进去的，比如第三个矩形到第一个矩形实际宽度应该是3，而如果简单的用矩形的编号相减（2-0）很明显是错误的。

• 为什么要给heights数组的结尾推入一个0？我个人理解是求得的每个高度所构成的最大矩形面积实际是在栈顶元素弹出时进行求解的，所以需要弹出每一个栈内元素之后才相当于遍历完成，否则会缺少条件。

• 结合代码和上一条分析来看，也就能一下明白了为什么在计算面积时使用的高度为heights[top]而不是heights[i]了。换言之就是当遇到比栈顶小的height，就是栈顶这个高度的矩形的宽不能再往右扩了，而因为我们采用的单调栈保证了栈内元素的单调递增，所以相当于也限定了这个高度的左侧宽度到哪里
  （我在这卡了好久想不明白，还是菜啊）