LeetCode 84 & 85：单调栈解题笔记
目录
题目概述
| 题目 | 核心思想 | 关联性 |
|---|---|---|
| 84. 柱状图中最大的矩形 | 单调栈求直方图最大面积 | 基础题 |
| 85. 最大矩形 | 将矩阵转化为直方图求解 | 进阶题 |
核心思想：矩阵最大矩形问题可以转化为直方图问题，通过逐行累加高度，将二维问题降维为一维直方图问题求解。
84. 柱状图中最大的矩形
问题描述
给定 n 个非负整数表示的柱状图，找到柱状图中能勾勒出的最大矩形面积。
解题思路
核心直觉
矩形的面积由高度和宽度决定。以第 i 根柱子的高度 h 作为矩形高度时，需要找到左右两侧第一个比它矮的柱子作为边界。
单调栈优化
暴力解法对每根柱子左右扫描的时间复杂度为 O(N²)，通过单调栈可在 O(N) 时间内完成。
栈的性质：维护一个递增栈，栈中存放柱子的索引。
- 当
heights[i] >= heights[st.top()]时：将索引 i 入栈 - 当
heights[i] < heights[st.top()]时：弹出栈顶tp，计算以其为高度的矩形面积
关键公式
高度 h = heights[tp]
左边界 left_idx = st.empty() ? -1 : st.top() // 弹出后的新栈顶
右边界 = i // 当前遍历位置
宽度 w = i - left_idx - 1
面积 = h * w
哨兵技巧
在数组末尾添加高度 0，确保所有柱子都能出栈并参与计算。
代码实现
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int max_area = 0;
stack<int> st;
heights.push_back(0); // 哨兵元素
int n = heights.size();
for (int i = 0; i < n; i++) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int h = heights[st.top()];
st.pop();
int left_idx = st.empty() ? -1 : st.top();
int w = i - left_idx - 1;
max_area = max(max_area, h * w);
}
st.push(i);
}
return max_area;
}
};
85. 最大矩形
问题描述
给定一个由 '0' 和 '1' 组成的二维矩阵，找到只包含 '1' 的最大矩形。
解题思路
降维转化
将二维矩阵问题转化为多次一维直方图问题：
- 初始化：heights[j] = 0
- 逐行遍历：
- 调用直方图算法：对每一行的 heights 数组调用 LeetCode 84 的解法
关键细节
'0'的出现会切断连续矩形，高度必须重置为 0- 每个元素最多入栈出栈一次，整体时间复杂度为 O(M×N)
代码实现
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int m = matrix.size();
int n = matrix[0].size();
int max_area = 0;
vector<int> heights(n + 1, 0); // 末尾 0 作为哨兵
for (int i = 0; i < m; i++) {
// 更新高度
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
// 单调栈求解
stack<int> st;
for (int j = 0; j <= n; j++) {
while (!st.empty() && heights[j] < heights[st.top()]) {
int h = heights[st.top()];
st.pop();
int left_idx = st.empty() ? -1 : st.top();
int w = j - left_idx - 1;
max_area = max(max_area, h * w);
}
st.push(j);
}
}
return max_area;
}
};
常见错误
// ❌ 错误写法
mx = max(mx, w * left_idx); // left_idx 是索引，不是高度
// ✅ 正确写法
mx = max(mx, w * h); // h 是实际高度值
复杂度分析
| 题目 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 84. 直方图 | O(N) | O(N) |
| 85. 矩阵 | O(M×N) | O(N) |
核心代码模板
// 84 题模板
int largestRectangleArea(vector<int>& heights) {
heights.push_back(0);
stack<int> st;
int max_area = 0;
for (int i = 0; i < heights.size(); i++) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int h = heights[st.top()];
st.pop();
int left = st.empty() ? -1 : st.top();
max_area = max(max_area, h * (i - left - 1));
}
st.push(i);
}
return max_area;
}
要点总结
- 单调栈：维护递增序列，找到左右边界
- 宽度公式：
w = i - left - 1 - 哨兵技巧：末尾加 0 确保所有元素出栈
- 降维思想：85 题将二维转化为一维直方图
提示：栈为空时左边界取 -1 和末尾哨兵位是两个容易忽略的关键细节。