84. 柱状图中最大的矩形

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

单调栈的应用。
单调栈的题是有套路的，先做几个入门题学习一下套路，在做这个。
入门题：
#739 每日温度
#503 下一个更大元素 II

然后回到本题
思路：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-by-ikaruga/
用单调栈的方法找到向左和向右的边界，主要是找到右边界，左边界用了Trick办法，很巧的方法。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        stack<int> st;
        int max_value = 0;
        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[st.top()] > heights[i]) {
                int cur = st.top();
                st.pop();
                int left = st.top() + 1;
                int right = i - 1;
                int area = (right - left + 1) * heights[cur];
                max_value = max(max_value, area);
            }
            st.push(i);
        }
        return max_value;
        


    }
};