力扣-单调栈-84 柱状图中最大的矩形

思路和时间复杂度

1. 思路：利用单调栈找到比当前元素小的第一个元素，此时在栈中的元素顺序从栈头到栈底是递降的，然后栈顶元素的下一个元素，就是比当前元素小的前一个元素，这样计算以当前元素（栈顶）作为高的矩形有多大即可。
2. 时间复杂度：       

代码

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        stack<int> st;
        st.push(0);

        int res = 0;
        for(int i = 1; i < heights.size(); i++){
            if(heights[i] > heights[st.top()]){
                st.push(i);
            }else if(heights[i] == heights[st.top()]){
                st.pop();
                st.push(i);
            }else{
                // 栈口元素找到右侧第一个比栈口元素小的i
                while(!st.empty() && heights[i] < heights[st.top()]){
                    int mid = st.top();
                    st.pop();
                    if(!st.empty()){
                        int left = st.top();
                        res = max(res, heights[mid] * (i - left - 1));
                    }
                }
                st.push(i);
            }
        }
        return res;
    }
};