84. Largest Rectangle in Histogr

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

栈里面存的是每个元素之前的那个元素是左边离它最近的比它小的。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int res = 0;
        heights.push_back(-1);
        for(int i = 0; i < heights.size(); i++) {
            while(!st.empty() && heights[st.top()] >= heights[i]) {
                int h = heights[st.top()];
                st.pop();
                int l = st.empty() ? -1 : st.top();
                int w = i - l - 1;
                res = max(res, w * h);
            }
            st.push(i);
        }
        return res;
    }
};