首页 > 上网技巧 > LeetCode 84. 柱状图中最大的矩形

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

时间:2021-01-02 21:51 作者:QQ地带 我要评论

题目描述
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
 
求在该柱状图中,能够勾勒出来的矩形的最大面积。
 
样例
输入: [2,1,5,6,2,3]
输出: 10
基础
单调栈是这道题的基础,我们用它来求区间中每一个数左边、右边最近的比它小的数。不会的同学先刷模板题ACWing 830 单调栈
 
算法1
(单调栈) O(n)O(n)
思路
维护一个单调栈,求出每一个柱子左、右两边最近的比它自身小的两根柱子,两根柱子之间就是这根柱子能构成的最大矩形
单调栈的头尾放置两个足够小(0)的柱子充当哨兵,统一编码形式,用处分别是:尾哨兵确保所有柱子都会被计算,头哨兵确保每次计算的左边界都正确。
* 第一次做的时候,光看思路有点懵,建议结合代码,模拟下样例,再思考整个逻辑的正确性。
 
时间复杂度
每个柱子入栈一次,出栈一次,出入栈均常数复杂度,故复杂度O(N)O(N).
 
C++ 代码
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        vector<int> st; // 单调栈,存待计算面积的柱子
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        int n = heights.size();
        int ans = 0;
        for(int i = 0; i<n; i++){
            while(!st.empty() && heights[st.back()] > heights[i]){
                // cur代表以这根柱子为中心,形成矩形并计算面积
                int cur = st.back();
                st.pop_back();
                // left代表左边最近小于自身的后面一根柱子
                int left = st.back() + 1;
                // right代表右边最近小于自身的前面一根柱子
                int right = i - 1;
                ans = max(ans, (right - left + 1) * heights[cur]);
            }
            st.push_back(i);
        }
        return ans;
    }
};
 
 

标签: LeetCode
顶一下
(0)
0%
踩一下
(0)
0%

Google提供的广告