最大矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
题目分析
- 想要知道最大矩形，肯定先要知道每根柱子怎么形成矩形的
- 对柱子 i，高度为 hi，以i为中心往两边扩展，只要碰到的柱子高度 Hj>=hi，那么形成的矩形必然是以 hi 为高构造。
- 假如 Hj<hi，那么这个矩形的高就是新的 Hj，而这个 Hj 构造的矩形必然会出现在以柱子 j 为中心扩展的时候，所以不必考虑降低现在的高度。
- 所以对柱子 i 的扩展，往左右两边找，碰到矮的停下来，确定两边边界，边界高度 Hj>=hi，这个即是这个 i 自己能做出来的最大矩形。
可以双重循环扫描，但不是重点，这里学习题解大神的栈思路。
题解分析：栈保留边界
首先有一层主循环遍历所有柱子，从左到右，当前柱子为 i。
我们目的是要找i的两个边界，因为是从左到右扫描，即我们可以顺手找到 i 的右边界。只要扫描时碰到比 i 矮的就知道这个是右边界了。
但是碰到比 i 高或者相等的柱子 j 怎么办呢？j 不会是 i 的边界 ，但我们也要找 j 的边界。因此我们要把未处理的 i 和 j 都留下来。
而继续往后找的时候， i 的右边界x 必然是 j 的右边界或者之外 （hi<=hj) 。
因此对于下一个柱子 x：
4.1 假如我们先判断 x 是不是 i 的边界，假如它是，它也不一定就是 j 的右边界 ，我们还得用 x 和 j 比较一次。假如它不是，它也不一定就不是 j 的右边界，还是得 x j 比较一次，所以先判定 i 的边界很鸡肋。
4.2 假如先判断 x 是不是更高的 j 的右边界，假如它不是，那么肯定也不是 i 的边界，假如它是，那么可以继续判定是不是更矮的 i 的右边界。因此，我们的扫描过程是这样的，从左到右，且保留的柱子高度递增（因为只要更高的才会保留，否则是作为右边界判定）。
且判定的顺序是高的在前，低的在后，即新的在前，旧的在后，因此保留柱子的数据结构是：栈。
因此遇到一个新柱子，与栈顶比较，更高则继续压栈。更低则是栈顶的右边界，然后栈顶出栈，判定是不是下一个栈顶的右边界。右边界解决了，我们还需要确定每个柱子 i 的左边界，左边界肯定在左边 ， 并且左边界也要比 i 矮，而我们的栈又是高度递增的= =+显然，我们可以利用出栈过程。
在栈顶确定了右边界，然后出栈的时候：
6.1 下面的那个柱子高度大于【栈顶右边界高度Hr】，那么这个柱子不是左边界，而可以组成这个矩形（因为有右边界后，矩形最低高度是Hr，只要高于Hr，都是）我们继续出栈寻找即可。
6.2 即一直出栈，直到出了个高度小于等于【栈顶右边界高度Hr】的柱子 x ，那么 x 就是上面这个矩形的左边界。
出栈到边界了怎么办？在数组开头预备一个0作为栈底标志位结束出栈。
同样压栈到边界了怎么办？在数组结尾预备一个0作为启动出栈的标志位。
- 此时 i 的左右边界都能找到，高度为 i ，计算面积。
总之精髓在于出栈过程，从栈顶的右边界，一直出栈到满足的左边界，中间这些柱子形成当前最大矩形。
题解代码
class Solution {
public:
int largestRectangleArea(vector<int>& heights)
{
//题解学习
std::stack<int> Lefts;
heights.insert(heights.begin(),0);//补0作为边界判断
heights.insert(heights.end(),0);
int result=0;
int temp;
for(int i=0;i<heights.size();i++)
{
//栈单调递增，当碰到一个i 比栈顶矮，则它必是栈顶的右边界
//再逐渐出栈，每次出栈循环，都是栈顶作为中心，而栈单调递增，栈顶下面一个更矮的必是栈顶的左边界，左右边界确定，则栈顶位置能形成的矩阵面积可计算完毕。
//直到栈顶比 i 还矮，那 i 就不能作为右边界了 ，栈顶此时的右边界也找不到，则 i 入栈待命当左边界，然后for下一轮
while(Lefts.empty()!=true && heights[Lefts.top()]>heights[i])//找到比栈顶矮的柱子，即栈顶柱子的右边界
{
temp=Lefts.top();
Lefts.pop();
result = max(result, (i - Lefts.top()-1)*heights[temp]);
}
Lefts.push(i);
}
return result;
}
};
