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.

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 =10unit.

For example,
Given height =[2,1,5,6,2,3],
return10.

思路：
用堆栈计算每一块板能延伸到的左右边界
对每一块板
堆栈顶矮，这一块左边界确定，入栈
堆栈顶高，堆栈顶右边界确定，出栈，计算面积
入栈时左边界确定
出栈时右边界确定
堆栈里元素是递增的
本质：中间的短板没有用！
复杂度 O(n)
代码如下：

class Solution {
    public:
    int largestRectangleArea(vector<int> &height) {
        stack<int> s;
        int len=height.size();
        int maxArea=0;
        //i可超出len边界
        for(int i=0;i<=len;i++)
        {
            //直方图的边界处理, 如果刚好超边界, 则当前高度为0
            int cur = (i == len ? 0 : height[i]);
            if (s.empty() || cur >= height[s.top()]) {
                s.push(i);
            } else {
                int p = s.top();
                s.pop();
                // 左边界, 如果stack已空则左边界为0, 否则为stack.peek()+1
                int left = (s.empty() ? 0 : s.top() + 1);
                maxArea =max(maxArea, height[p] * (i - left));
                i--;
            }
        }
        return maxArea;
    }
};