题目描述
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
样例
输入: [2,1,5,6,2,3]
输出: 10
基础
单调栈是这道题的基础,我们用它来求区间中每一个数左边、右边最近的比它小的数。不会的同学先刷模板题ACWing 830 单调栈
算法1
(单调栈) $O(n)$
思路
维护一个单调栈,求出每一个柱子左、右两边最近的比它自身小的两根柱子,两根柱子之间就是这根柱子能构成的最大矩形
单调栈的头尾放置两个足够小(0)的柱子充当哨兵,统一编码形式,用处分别是:尾哨兵确保所有柱子都会被计算,头哨兵确保栈中始终有一个元素,使得当左边最近柱子是左边界时也能被正确计算。
* 第一次做的时候,光看思路有点懵,建议结合代码,模拟下样例,再思考整个逻辑的正确性。
时间复杂度
每个柱子入栈一次,出栈一次,出入栈均常数复杂度,故复杂度$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 85.最大矩形
二维问题,先枚举其中一维转换为一维问题,再用前面的算法解决。