84. 柱状图中最大的矩形

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;
        


    }
};
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容