LeetCode 题解工作台
最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 示例 1： 输入： matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["…
5
题型
7
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们把每一行视为柱状图的底部，对每一行求柱状图的最大面积即可。 具体地，我们维护一个与矩阵列数相同的数组 ，其中 表示以当前行为底部、以第 列为高度的柱子的高度。对于每一行，我们遍历每一列：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6 解释：最大矩形如上图所示。
示例 2：
输入：matrix = [["0"]] 输出：0
示例 3：
输入：matrix = [["1"]] 输出：1
提示：
rows == matrix.lengthcols == matrix[0].length1 <= rows, cols <= 200matrix[i][j]为'0'或'1'
解题思路
方法一：单调栈
我们把每一行视为柱状图的底部，对每一行求柱状图的最大面积即可。
具体地，我们维护一个与矩阵列数相同的数组 ，其中 表示以当前行为底部、以第 列为高度的柱子的高度。对于每一行，我们遍历每一列：
- 如果当前元素为 '1'，则将 加 。
- 如果当前元素为 '0'，则将 置为 。
然后，我们使用单调栈算法计算当前柱状图的最大矩形面积，并更新答案。
单调栈的具体做法如下：
- 初始化一个空栈 ，用于存储柱子的索引。
- 初始化两个数组 和 ，分别表示每个柱子左侧和右侧第一个小于当前柱子的柱子的索引。
- 遍历柱子高度数组 ，首先计算每个柱子左侧第一个小于当前柱子的柱子的索引，并存储在 中。
- 然后反向遍历柱子高度数组 ，计算每个柱子右侧第一个小于当前柱子的柱子的索引，并存储在 中。
- 最后，计算每个柱子的最大矩形面积，并更新答案。
时间复杂度 ，其中 表示 的行数， 表示 的列数。
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
heights = [0] * len(matrix[0])
ans = 0
for row in matrix:
for j, v in enumerate(row):
if v == "1":
heights[j] += 1
else:
heights[j] = 0
ans = max(ans, self.largestRectangleArea(heights))
return ans
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
stk = []
left = [-1] * n
right = [n] * n
for i, h in enumerate(heights):
while stk and heights[stk[-1]] >= h:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
h = heights[i]
while stk and heights[stk[-1]] >= h:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you recognize how row-by-row state transitions reduce redundant computations?
- question_mark
Can you apply a monotonic stack to track maximal rectangle boundaries efficiently?
- question_mark
Will you update height, left, and right arrays correctly for each row to compute areas?
常见陷阱
外企场景- error
Failing to reset height to zero for '0' cells leads to incorrect cumulative heights.
- error
Incorrectly computing left and right boundaries can result in underestimating maximal rectangle width.
- error
Assuming maximal rectangle always starts at the first '1' without proper DP tracking misses valid areas spanning multiple rows.
进阶变体
外企场景- arrow_right_alt
Compute maximal square instead of rectangle using similar height tracking DP.
- arrow_right_alt
Find the largest rectangle of 1's in a circular matrix wrapping rows or columns.
- arrow_right_alt
Return coordinates of the maximal rectangle instead of just its area.