85. 最大矩形
题目描述
输入一个 rows x cols 的矩阵 matrix，每格是字符 '0' 或 '1'。
在矩阵中找一个由若干连续行、连续列围成的矩形区域，要求里面的格子全是 '1'。
返回这种区域最多能包含多少个格子，即最大面积。没有 '1' 时返回 0。
示例 1
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6
解释：第 1、2 行（从 0 计）的第 2 到第 4 列全是 '1'，面积 2 * 3 = 6。
示例 2
输入：matrix = [["0"]] 输出：0
解释：矩阵中没有 '1'。
示例 3
输入：matrix = [["1"]] 输出：1
数据范围
rows == matrix.lengthcols == matrix[0].length1 <= rows, cols <= 200matrix[i][j]只会是'0'或'1'。
解题思路：逐行转为柱状图 + 单调栈
逐行把矩阵看成柱状图：heights[j] 是以当前行为底、第 j 列向上连续 "1" 的个数。每行都用单调栈求一次“柱状图中最大矩形”：栈中下标的高度递增，当 heights[j] 不高于栈顶时弹出栈顶，它的右边界是 j，左边界是新栈顶，宽度 = j - 新栈顶 - 1。末尾多放一个高度 0 的哨兵，保证栈被清空。
为什么正确
栈底是 -1，其余下标对应的高度严格递增；相邻两个下标之间的柱子都不低于上面那个。
复杂度分析
时间 O(mn)，每行每个下标最多入栈出栈各一次；空间 O(n)。
易错点
矩阵元素是字符 "1"/"0"，不是数字。弹栈后宽度要用新的栈顶计算（j - stack[-1] - 1），不是 j - 被弹下标。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
n = len(matrix[0])
heights = [0] * (n + 1)
best = 0
for row in matrix:
for j in range(n):
heights[j] = heights[j] + 1 if row[j] == '1' else 0
stack = [-1]
for j in range(n + 1):
while stack[-1] != -1 and heights[stack[-1]] >= heights[j]:
h = heights[stack.pop()]
best = max(best, h * (j - stack[-1] - 1))
stack.append(j)
return bestclass Solution {
public int maximalRectangle(char[][] matrix) {
int n = matrix[0].length;
int[] heights = new int[n + 1];
int best = 0;
for (char[] row : matrix) {
for (int j = 0; j < n; j++) {
heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
}
int[] stack = new int[n + 2]; int top = 0; stack[0] = -1;
for (int j = 0; j <= n; j++) {
while (stack[top] != -1 && heights[stack[top]] >= heights[j]) {
int h = heights[stack[top--]];
best = Math.max(best, h * (j - stack[top] - 1));
}
stack[++top] = j;
}
}
return best;
}
}class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n = matrix[0].size();
vector<int> heights(n + 1, 0);
int best = 0;
for (auto& row : matrix) {
for (int j = 0; j < n; j++) {
heights[j] = row[j] == '1' ? heights[j] + 1 : 0;
}
vector<int> stack = {-1};
for (int j = 0; j <= n; j++) {
while (stack.back() != -1 && heights[stack.back()] >= heights[j]) {
int h = heights[stack.back()]; stack.pop_back();
best = max(best, h * (j - stack.back() - 1));
}
stack.push_back(j);
}
}
return best;
}
};func maximalRectangle(matrix [][]byte) int {
n := len(matrix[0])
heights := make([]int, n+1)
best := 0
for _, row := range matrix {
for j := 0; j < n; j++ {
if row[j] == '1' {
heights[j]++
} else {
heights[j] = 0
}
}
stack := []int{-1}
for j := 0; j <= n; j++ {
for stack[len(stack)-1] != -1 && heights[stack[len(stack)-1]] >= heights[j] {
h := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
if w := h * (j - stack[len(stack)-1] - 1); w > best {
best = w
}
}
stack = append(stack, j)
}
}
return best
}var maximalRectangle = function(matrix) {
const n = matrix[0].length;
const heights = new Array(n + 1).fill(0);
let best = 0;
for (const row of matrix) {
for (let j = 0; j < n; j++) {
heights[j] = row[j] === '1' ? heights[j] + 1 : 0;
}
const stack = [-1];
for (let j = 0; j <= n; j++) {
while (stack[stack.length - 1] !== -1 && heights[stack[stack.length - 1]] >= heights[j]) {
const h = heights[stack.pop()];
best = Math.max(best, h * (j - stack[stack.length - 1] - 1));
}
stack.push(j);
}
}
return best;
};function maximalRectangle(matrix: string[][]): number {
const n = matrix[0].length;
const heights = new Array(n + 1).fill(0);
let best = 0;
for (const row of matrix) {
for (let j = 0; j < n; j++) {
heights[j] = row[j] === '1' ? heights[j] + 1 : 0;
}
const stack = [-1];
for (let j = 0; j <= n; j++) {
while (stack[stack.length - 1] !== -1 && heights[stack[stack.length - 1]] >= heights[j]) {
const h = heights[stack.pop()!];
best = Math.max(best, h * (j - stack[stack.length - 1] - 1));
}
stack.push(j);
}
}
return best;
}其他解法
优化暴力对每个右下角向上枚举高度，O(m²n)；单调栈把每一行看成一张柱状图，复用第 84 题的 O(n) 算法，总共 O(mn)。
解法 2：使用柱状图的优化暴力方法 时间 O(m²n)，空间 O(mn)
先算出 left[i][j]：第 i 行以第 j 列结尾、向左连续的 1 的个数。然后把每个格子 (i, j) 当作矩形的右下角，向上逐行扩展：矩形宽度是这些行的 left 值的最小值，高度是扩展的行数，面积取最大。宽度变成 0 就可以提前停止。
思路直白，只用到前缀计数和枚举，容易想到。每个格子最多向上走 m 行，总时间 O(m²n)，比单调栈慢一个 m 的因子。
from typing import List
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m, n = len(matrix), len(matrix[0])
# left[i][j]：以 (i, j) 结尾、向左连续 1 的个数
left = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
left[i][j] = (left[i][j - 1] if j > 0 else 0) + 1
best = 0
for i in range(m):
for j in range(n):
width = left[i][j]
k = i
# 以 (i, j) 为右下角，向上逐行扩展
while k >= 0 and width > 0:
width = min(width, left[k][j])
best = max(best, width * (i - k + 1))
k -= 1
return bestclass Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] left = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matrix[i][j] == '1') left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
int best = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int width = left[i][j];
for (int k = i; k >= 0 && width > 0; k--) {
width = Math.min(width, left[k][j]);
best = Math.max(best, width * (i - k + 1));
}
}
}
return best;
}
}class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> left(m, vector<int>(n, 0));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matrix[i][j] == '1') left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
int best = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int width = left[i][j];
for (int k = i; k >= 0 && width > 0; k--) {
width = min(width, left[k][j]);
best = max(best, width * (i - k + 1));
}
}
}
return best;
}
};func maximalRectangle(matrix [][]byte) int {
m, n := len(matrix), len(matrix[0])
left := make([][]int, m)
for i := 0; i < m; i++ {
left[i] = make([]int, n)
for j := 0; j < n; j++ {
if matrix[i][j] == '1' {
if j > 0 {
left[i][j] = left[i][j-1] + 1
} else {
left[i][j] = 1
}
}
}
}
best := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
width := left[i][j]
for k := i; k >= 0 && width > 0; k-- {
width = min(width, left[k][j])
best = max(best, width*(i-k+1))
}
}
}
return best
}var maximalRectangle = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const left = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (matrix[i][j] === '1') left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
let best = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let width = left[i][j];
for (let k = i; k >= 0 && width > 0; k--) {
width = Math.min(width, left[k][j]);
best = Math.max(best, width * (i - k + 1));
}
}
}
return best;
};function maximalRectangle(matrix: string[][]): number {
const m = matrix.length, n = matrix[0].length;
const left: number[][] = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (matrix[i][j] === '1') left[i][j] = (j > 0 ? left[i][j - 1] : 0) + 1;
let best = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let width = left[i][j];
for (let k = i; k >= 0 && width > 0; k--) {
width = Math.min(width, left[k][j]);
best = Math.max(best, width * (i - k + 1));
}
}
}
return best;
}