84 柱状图最大的矩形
https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
解法一: 暴力枚举
枚举宽:枚举左边界,再枚举右边界
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
int n = heights.size();
for(int i = 0; i < n; i++){
int minHeight = heights[i];
for(int j = i; j < n; j++){
minHeight = min(minHeight, heights[j]);
ans = max(ans, (j - i + 1) * minHeight);
}
}
return ans;
}
};
枚举高:
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
int n = heights.size();
// 枚举每根柱子的高度
for(int mid = 0; mid < n; mid++){
int height = heights[mid];
int left = mid, right = mid;
// 如果左右柱子比当前枚举的柱子高,那么矩形的高度仍然为当前枚举柱子的高度heights[mid]
while(left - 1 >= 0 && heights[left - 1] >= height) --left;
while(right + 1 < n && heights[right + 1] >= height) ++right;
// 注意这里left和right都指向最后一个比枚举柱子高度大的柱子
// 与单调栈做法不同,这里为right - left + 1(单调栈是right - left - 1)
ans = max(ans, (right - left + 1) * height);
}
return ans;
}
};
可以发现,这两种暴力方法的时间复杂度均为$ O(N^2)$,会超出时间限制,我们必须要进行优化。考虑到枚举「宽」的方法使用了两重循环,本身就已经需要 \(O(N^2)\)的时间复杂度,不容易优化,因此我们可以考虑优化只使用了一重循环的枚举「高」的方法。
解法二: 单调栈
朴素版
单调栈常用于查找比它大的第一个数 or 比它小的第一个数
单调递增栈:栈内离栈顶越近(下标越大),栈元素越大;栈顶元素为栈内最大
- 当有新元素进入,如果新元素比栈顶元素大,直接入栈。
- 当有新元素进入,如果新元素比栈顶元素小,栈弹出,直到满足新元素比栈顶元素大,再将新元素入栈。
由此可见,新元素C使栈顶元素A弹出后,下一个栈顶元素B是A左边第一个比B小的元素,新元素C是A右边第一个比C小的元素
由暴力枚举高的解法可知道,我们枚举高度后需要分别往两边寻找比它矮的第一个柱子(数),因此可以使用单调栈
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
int n = heights.size();
vector<int> left(n), right(n);
stack<int> stk;
for(int i = 0; i < n; i++){
while(!stk.empty() && heights[stk.top()] >= heights[i]) stk.pop();
left[i] = (stk.empty() ? -1 : stk.top());
stk.push(i);
}
stk = stack<int>();
for(int i = n - 1; i >= 0; i--){
while(!stk.empty() && heights[stk.top()] >= heights[i]) stk.pop();
right[i] = (stk.empty() ? n : stk.top());
stk.push(i);
}
for(int i = 0; i < n; i++){
// right 和 left 都指向第一个比枚举柱子小的柱子,因此不包含left 和 right
// 宽度计算为: (right - 1) - (left + 1) + 1 = right - left - 1
ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
};
复杂度分析
- 时间复杂度:O(N)。
- 空间复杂度:O(N)。
每一个位置只会入栈一次(在枚举到它时),并且最多出栈一次。
因此当我们从左向右/总右向左遍历数组时,对栈的操作的次数就为 O(N)。所以单调栈的总时间复杂度为 O(N)。
优化版
对上述进行优化
新元素C使栈顶元素A弹出后,下一个栈顶元素B是A左边第一个比B小的元素,新元素C是A右边第一个比C小的元素
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int len = heights.size() + 2;
vector<int> height(len);
// 在heights数组基础上在头尾加上0元素
// 这是因为以heights[0](heights[heights.size() - 1])作为柱子高度时,缺少左边界(右边界)
// 为其补上左右边界,使其能够计算heights[0](heights[heights.size() - 1])作为柱子高度时的面积
height[0] = 0;
height[len - 1] = 0;
for(int i = 1; i < len - 1; i++)
height[i] = heights[i - 1];
stack<int> stk;
int ans = 0;
for(int i = 0; i < len; i++){
while(!stk.empty() && height[i] < height[stk.top()]){
// 新元素i让栈弹出,栈顶元素为stk.top()
int idx = stk.top();
stk.pop();
// 这里的stk.top()为弹出后的下一个栈顶元素
int w = i - stk.top() - 1;
// 高度为最初的栈顶元素
ans = max(ans, w * height[idx]);
}
// 没有弹出时不需要计算面积
stk.push(i);
}
return ans;
}
};
复杂度分析
- 时间复杂度:O(N)。
- 空间复杂度:O(N)。