84. Largest Rectangle in Histogram
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.
参考一下大神的总结：LeetCode Monotone Stack Summary 单调栈小结
我们可以看到，直方图矩形面积要最大的话，需要尽可能的使得连续的矩形多，并且最低一块的高度要高。有点像木桶原理一样，总是最低的那块板子决定桶的装水量。那么既然需要用单调栈来做，首先要考虑到底用递增栈，还是用递减栈来做。我们想啊，递增栈是维护递增的顺序，当遇到小于栈顶元素的数就开始处理，而递减栈正好相反，维护递减的顺序，当遇到大于栈顶元素的数开始处理。那么根据这道题的特点，我们需要按从高板子到低板子的顺序处理，先处理最高的板子，宽度为1，然后再处理旁边矮一些的板子，此时长度为2，因为之前的高板子可组成矮板子的矩形 ，因此我们需要一个递增栈，当遇到大的数字直接进栈，而当遇到小于栈顶元素的数字时，就要取出栈顶元素进行处理了，那取出的顺序就是从高板子到矮板子了，于是乎遇到的较小的数字只是一个触发，表示现在需要开始计算矩形面积了，为了使得最后一块板子也被处理，这里用了个小trick，在高度数组最后面加上一个0，这样原先的最后一个板子也可以被处理了。由于栈顶元素是矩形的高度，那么关键就是求出来宽度，那么跟之前那道Trapping Rain Water一样，单调栈中不能放高度，而是需要放坐标。由于我们先取出栈中最高的板子，那么就可以先算出长度为1的矩形面积了，然后再取下一个板子，此时根据矮板子的高度算长度为2的矩形面积，以此类推，直到数字大于栈顶元素为止，再次进栈，巧妙的一比！
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
if(n==0) return 0;
if(n==1) return heights[0];
int res = 0;
//需要增加一个0将最后栈内剩余的元素弹出栈进行计算
heights.push_back(0);
stack<int> s;
for(int i=0;i<n+1;++i) {
//递增栈如果大于栈顶元素则入栈
if(s.empty()||heights[i]>heights[s.top()])
s.push(i);
else {
//将栈内大于当前值得元素依次出栈计算大小
while(!s.empty()&&heights[i]<heights[s.top()]) {
int t = s.top();
s.pop();
int h = heights[t];
int w = 0;
//宽度需要考虑到之前弹出的长度 如果弹出当前计算的元素之后
//栈不空则栈顶元素（下标）则为当前计算元素的前一个高度小于该
//元素的下标 最大宽度应该从此开始计算 以免缺漏
if(!s.empty())
w = i - s.top() - 1;
else //如果栈已经为空了，说明前面的元素都比当前元素大，或者
//当前元素就是第一个元素，所以宽度应该从0开始计算
w = i - 0;
res = max(res,h*w);
}
s.push(i);
}
}
return res;
}
};
分析：
这道题目采用的还是单调栈的套路。考虑什么时机处理矩形面积的计算。当出现连续递增的矩形的时候是不需要计算的，因为此时往后会有更大的可能出现更大的矩形面积，当出现不满足高度递增的时候，说明此时出现断层，由于短板效应，前面所有比该断层值大的位置都该计算其最大面积，因为此处断层，后面再出现的以及和前面这些的计算无关，所以出现递减的时候是计算处理的触发点，所以采用单增栈进行存储。
- 如果时间复杂度乍一看是o(n^2)的问题，如果输入在某些维度上是大小不一的输入，有大小关系，可以考虑单调栈进行优化时间复杂度，单调栈如果可以成功那么时间复杂度将被减小至o(n)。
