题解 | #直方图内最大矩形#

#include <stack>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型vector 
     * @return int整型
     */
    int largestRectangleArea(vector<int>& heights) {
        int result = 0 ;
        heights.insert(heights.begin(), result) ;
        heights.push_back(result) ;
        stack<int> st ;
        st.push(0) ;

        for (int i = 1; i<heights.size(); i++) 
        {
            while (!st.empty() && heights[i] < heights[st.top()]) 
            {
                int tmp = st.top() ;
                st.pop(); 
                result = max((i-st.top()-1)*heights[tmp], result) ;
            }
            st.push(i) ;
        }
        return result ;
    }
};

左右找最小