本文共 1487 字，大约阅读时间需要 4 分钟。

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,

寻找柱状图中的最大矩形，给出的是柱状图的一系列高度值，每个值对应的水平宽度为1。

一个比较巧妙的办法是借助栈实现，思路描述如下：

注释1：一个问题是，为什么可以这样呢？嗯，仔细思考一下，实际上，当我们进行pop操作时，取出来的高度就是下一栈顶和当前i之间的最小高度值（注意不包括栈顶和i，是开区间），因为凡是比当前高度大的值，在pop出当前高度的时候，就已经被pop出来了（因为栈内始终是升序呀），这样也就计算出了一系列矩形面积值。

注释2：另外，这种优化也是十分巧妙的，因为它避免了大量重复的运算，当一个序列为递增序列时，例如{1，2，3，4}，如果我们采用暴力方法计算时，对于任意区间[i,j]，因为首元素始终是最小的，所以后续一系列区间（增加j时）的计算其实都是没有必要的，但是利用栈，将这种计算延后（实际上也通过栈来帮助我们识别出这种单调性），每次pop出的时候再计算，简化了一系列重复计算的步骤。

注释3：单调栈

class Solution {public:    int largestRectangleArea(vector
   
    & heights) {        heights.push_back(0);        int n=heights.size(),i=0,maxArea=0;        stack
    
      index;        while(i
     
      =heights[index.top()])                index.push(i++);            else{                int tp=index.top();                index.pop();                maxArea=max(maxArea,heights[tp]*(index.empty()?i:i-index.top()-1));            }        }        return maxArea;    }};