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;
}
};
