Largest Rectangle in Histrogram

https://leetcode.com/problems/largest-rectangle-in-histogram/

1）暴力解法是n^2；

2）使用单调栈是n；

3）n是遍历每一个木头，并假设这个木头是最矮的木头，求出以此为基础的当前最大面积（只有一个）；

4）找出某一个数左边右边第一个比他大或者小的数，在O1时间复杂度里；

5）当一个数进去栈里，左边第一个比他小的就是他左边的那个数；

6）右边呢？当这个数被pop出去的时候，把他踢走的那个数就是右边第一个比他小的数；

7）例子：2 5 6 在下一个2进栈的时候，6被pop出去了，所以左边比6小的是5，右边比6小的是2；

8）最后加一个-1就能把当前栈的所有数踢走；

9）等于的情况？1，2，2，2不是单调栈；

code

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if(n == 0)
        {
            return 0;
        }

        heights.push_back(-1);
        vector<int> stack;
        int max_area = INT_MIN;

        for(int i = 0; i<n+1; i++)
        {
            while(!stack.empty() && heights[i] <= heights[stack.back()])
            {
                int h = heights[stack.back()];
                stack.pop_back();
                int w = stack.empty()?i:i-stack.back()-1;
                //cout<<h<<" "<<w<<endl;
                max_area = max(max_area, h*w);
            }
            stack.push_back(i);
        }

        return max_area;
    }
};