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.
Example:
Input: [2,1,5,6,2,3] Output: 10
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3] 输出: 10
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
参考@力扣官方题解【柱状图中最大的矩形】中单调栈的思路。
直观的思路：确定一个位置 i 的左右边界，ans = max(ans, (right - left - 1) * height[i] )即可；
那么如何确定边界呢？
简单的方法：每次都从当前位置 i 开始向两边扩展，直到高度小于当前柱子位置；（重复的次数太多，且没有利用之前计算的结果）单调栈：栈中的元素全部按照递增/递减的规律排列。栈中总是保存递增元素的索引，当遇到比栈顶元素小的元素时，将栈顶元素依次出栈，直到栈顶元素小于当前元素时，便可确定左边界。这样就可以借助于之前计算的结果，降低时间复杂度；接下来详细介绍单调栈的用法，仍以获得左边界为例：
栈中元素为柱子的下标。假定原先柱子对应的高度如下： 按照单调栈的原理，下标0、1、2对应的高度呈递增状态，故依次入栈。此时栈中元素为[0，1，2]；当下标移至 3 时，height[0] < height[3]=2 < height[1] < height[2]， 故将2，1依次从栈中弹出。此时栈中元素为[0]，0即 下标为 3 柱子对应的左边界；注意：
在实际实现过程中，为了处理边界问题，常常设置哨兵。我的方法是，左边界的哨兵即栈中先存入-1，这样遇到-1就说明已经到达了最左边，不会继续出栈了；右边界的哨兵即栈中先存入height.size()，原理同上；
能不能一次遍历，就可以得到左右边界呢？（来自大佬的灵魂拷问）
当然可以，注意到：当位置 i 被弹出栈时，说明此时遍历到的位置 j 的高度小于height[i]，且 i 与 j 之间不存在小于height[i]的柱子（若有的话，i 就已经被提前弹出了）。那么位置 j 就是位置 i 的右边界，左边界就是 i 弹出后的栈顶元素；
即每出栈一个元素，即可同时确定其左右边界；
举例如下：
原数组如下，假设当前下标 j = 3，此时栈中元素为[0，1，2]； 由于height[3] < height[2]，元素2出栈，可以确定下标为2的柱子对应的左右边界：此时 j = 3 即为下标2对应的右边界，而出栈后的栈顶元素1，即为下标2对应的左边界；同理height[3] < height[1]，元素1也会出栈，具体操作同上；height[3] > height[0]，元素3放入栈中，此时栈中元素为[0，3]；
就直接暴力吧，双重循环O(n^2)，minHigh指定左右指针划定区间内的最小值，ans记录最大矩形面积：
class Solution { public: int largestRectangleArea(vector<int>& heights) { int ans = 0, minHigh = INT_MAX; for(int i = 0; i < heights.size(); i++){ minHigh = INT_MAX; for(int j = i; j < heights.size(); j++){ minHigh = min(minHigh, heights[j]); ans = max(ans, (j - i + 1) * minHigh); // cout<<ans<<endl; } } return ans; } };换一种思路，遍历所有的柱子，过程中，把当前遍历到的柱子（高度为h）作为最低的一根，然后向左右两边扩展，直到高度小于h的柱子，这样就可以划分一个区间，区间乘以h用来更新ans。（类似于寻找最长回文子串中的中心扩展法，时间复杂度仍为O(N^2)）
class Solution { public: int largestRectangleArea(vector<int>& heights) { int ans = 0; for(int i = 0; i < heights.size(); i++){ int left = i, right = i; while(left >= 0 && heights[left] >= heights[i]) left--; while(right < heights.size() && heights[right] >= heights[i]) right++; ans = max(ans, heights[i] * (right - left - 1)); } return ans; } };不出意外，还是超时了
欣赏了官方题解，发现第二搏中存在的可以改进的地方：由于每次扩展时，都是从当前位置向两边扩展，而没有利用到之前计算边界的结果，比如：
当遍历到下标为2的柱子时，可以得到两个边界值0，3 现在下标移至3，若按照第二搏中的方法，左右边界又要从下标3开始左右扩展，但是由于已经记录出了下标2的左右边界，且height[3]<height[2]，所以可以直接在下标2的左边界基础之上开始继续向左扩展维护一个单调栈，栈中总是保存递增元素的索引，当遇到比栈顶元素小的元素时，将栈顶元素依次出栈，这样就可以避免重复的扩展了。
从左向右使用一次单调栈，获得左边界；
从右向左使用一次单调栈，获得右边界；
再次遍历数组，ans = max(ans, heights[i] * (right[i] - left[i] - 1));获得最大矩形面积
class Solution { public: int largestRectangleArea(vector<int>& heights) { stack<int> s; // 单调栈 存放下标 vector<int> left(heights.size()), right(heights.size()); // 获得左边界 s.push(-1); // 左边界哨兵为-1 for(int i = 0; i < heights.size(); i++){ int tem = s.top(); while(tem != -1 && heights[tem] >= heights[i]){ s.pop(); tem = s.top(); } s.push(i); // 将当前柱子下标存入单调栈 left[i] = tem; } while(!s.empty()) s.pop(); // 获得右边界 s.push(heights.size()); // 右边界哨兵为heights.size() for(int i = heights.size() - 1; i >= 0; i--){ int tem = s.top(); while(tem != heights.size() && heights[tem] >= heights[i]){ s.pop(); tem = s.top(); } s.push(i); // 将当前柱子下标存入单调栈 right[i] = tem; } int ans = 0; for(int i = 0; i < heights.size(); i++){ ans = max(ans, heights[i] * (right[i] - left[i] - 1)); } return ans; } };时间方面和想象中还是有差距的。。。
单调栈+常数优化
只用一次遍历即可求出左右边界！
关键点：当位置 i 被弹出栈时，说明此时遍历到的位置 j 的高度小于height[i]，且 i 与 j 之间不存在小于height[i]的柱子（若有的话，i 就已经被提前弹出了）；
故左边界为 i 弹出后，栈顶的元素；右边界为当前的位置 j ；高度即弹出的 i 对应的height[i]；
class Solution { public: int largestRectangleArea(vector<int> &heights) { stack<int> s; int ans = 0; heights.push_back(0); // !!!为了保证最右边的元素也能被弹出且参与比较 故插入0 s.push(-1); // 哨兵 标明左边界 for (int i = 0; i < heights.size(); ++i) { while (s.top() != -1 && heights[s.top()] >= heights[i]) { int h = heights[s.top()]; s.pop(); ans = max(ans, (i - s.top() - 1) * h); } s.push(i); } return ans; } };好了一点（虽然感觉已经非常简洁了o(￣┰￣*)ゞ）
