最大矩形
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个仅包含 0 和 1、大小为 rows × cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1
示例 2
示例 3
模拟答题者思考
1. 暴力：枚举矩形的左上、右下角点，检查是否全为 1 再算面积——正确，但 O(rows²×cols²) 或带预处理的 O(rows²×cols²)，数据范围下太慢。
2. 固定高度：若矩形高度为 h、底边在第 i 行，则它等价于：在由「每列向上连续 1 的长度」形成的柱状图上，找高度至少为 h 的最大宽矩形——仍要枚举 h，不够干脆。
3. 逐行压缩：按行向下扫，维护 heights[j] = 以当前行为底、第 j 列向上连续 1 的个数。则任意底边在当前行的最大全 1 矩形，一定等于「当前 heights 作为柱状图」的最大矩形（LeetCode 84）。
4. 复用 #84：每行更新 heights 后，用单调栈 O(cols) 求该行柱状图最大面积；共 rows 行，总复杂度 O(rows×cols)。
5. 关键直觉：矩阵里的矩形底边只能落在某一行上；把问题拆成「底边在第 i 行」的若干子问题，子问题全是柱状图最大矩形。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
heights[j] | int[] | 定义：第 i 行处理完后，第 j 列中「以当前行为底、向上连续为 1」的柱子高度维护：扫到 matrix[i][j]=='1' 则 heights[j]+=1，否则置 0（0 截断竖条）更新：每处理完一行， heights 就是该行视角下的「柱状图」高度数组 |
row_ans | int | 定义：当前行对应柱状图上的最大矩形面积（即 #84 子问题答案） 维护：对固定 heights 用单调递增栈求最大矩形更新：每行扫完后计算一次，并入全局 ans |
st | stack<int> | 定义：#84 同款，存下标，栈内高度单调递增 维护：处理当前行 heights 时，在「当前更矮」处弹出并结算更新：每行重新清空或复用栈，对该行 heights 从左到右扫描 |
ans | int | 定义：所有行、所有合法矩形中的最大面积 维护： ans = max(ans, row_ans)更新：遍历完每一行后取 max |
落码步骤
1. 若矩阵为空返回 0；heights = [0] * cols，ans = 0
2. 对每一行 i：遍历列 j，matrix[i][j]=='1' 则 heights[j]+=1，否则 heights[j]=0
3. 调用柱状图最大矩形（单调栈 + 末尾高度 0 哨兵），得到 row_ans
4. ans = max(ans, row_ans)，处理完所有行后返回 ans
5. 栈逻辑与 #84 相同：while h < heights[st.top()] 弹出 mid，宽度 i - left - 1，更新答案
代码实现
class Solution:
def maximalRectangle(self, matrix: list[list[str]]) -> int:
if not matrix or not matrix[0]:
return 0
rows, cols = len(matrix), len(matrix[0])
heights = [0] * cols
ans = 0
def largest_in_row(h: list[int]) -> int:
st = []
row_ans = 0
for i, hi in enumerate(h + [0]): # 哨兵结算栈内剩余柱子
while st and hi < h[st[-1]]:
mid = st.pop()
left = st[-1] if st else -1
w = i - left - 1
row_ans = max(row_ans, h[mid] * w)
st.append(i)
return row_ans
for i in range(rows):
for j in range(cols):
if matrix[i][j] == "1":
heights[j] += 1
else:
heights[j] = 0
ans = max(ans, largest_in_row(heights))
return ansclass Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int rows = matrix.size(), cols = matrix[0].size();
vector<int> heights(cols, 0);
int ans = 0;
auto largestInRow = [&](vector<int>& h) {
stack<int> st;
int rowAns = 0;
h.push_back(0); // 哨兵
for (int i = 0; i < (int)h.size(); i++) {
while (!st.empty() && h[i] < h[st.top()]) {
int mid = st.top(); st.pop();
int left = st.empty() ? -1 : st.top();
int w = i - left - 1;
rowAns = max(rowAns, h[mid] * w);
}
st.push(i);
}
h.pop_back();
return rowAns;
};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == '1') heights[j]++;
else heights[j] = 0;
}
ans = max(ans, largestInRow(heights));
}
return ans;
}
};
// 时间 O(rows×cols)，空间 O(cols)复杂度分析
O(rows × cols)
O(cols)
常见坑
字符比较：矩阵元素是 '0'/'1' 字符，不是整数 1，C++/Java 要用引号。
忘记 heights[j]=0：遇到 0 必须清零该列竖条，否则会把上一段 1 错误延伸到本行。
每行都要跑完整柱状图算法：不能只对「变化了的列」偷懒，整行 heights 才是当前底边的正确柱状图。
必测边界 Case
matrix = [["0","0"],["0","0"]] → 0
matrix = [["1","1"],["1","1"]] → 4（整表矩形）
matrix = [["1","1","0","1"]] → 2（底边在该行，柱状图最大宽 2）
matrix = [["1"],["1"],["0"],["1"]] → 2（中间 0 截断，最大高度 2 的竖条）