leetcode 84. 柱状图中最大的矩形

/*
    单调栈维护一个递增的栈，对于h[i]如果大于栈顶元素就一直压栈
    否则，先弹出栈顶元素k,面积=h[k]*(i-1-st.top())；
    最后把栈清空，面积=h[k]*(i-1-st.top())；这时候的i=n
*/
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n=heights.size();
        stack<int> st;
        st.push(-1);
        int ans=0;
        for(int i=0;i<heights.size();i++)
        {
            while(st.top() != -1 && heights[st.top()] > heights[i])
            {
                int k=st.top();st.pop();
                ans=max(ans,heights[k]*(i-1-st.top()));
                //cout<<k<<endl;
            } 
            st.push(i);
        }
        while(st.top() != -1)
        {
            int k=st.top();st.pop();
            ans=max(ans,heights[k]*(n-1-st.top()));
        }
        return ans;
    }
};