难度: Hard
给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。
注意：此题 matrix 输入格式为一维 01 字符串数组。
示例 1：
输入：matrix = ["10100","10111","11111","10010"] 输出：6 解释：最大矩形如上图所示。
示例 2：
输入：matrix = [] 输出：0
示例 3：
输入：matrix = ["0"] 输出：0
示例 4：
输入：matrix = ["1"] 输出：1
示例 5：
输入：matrix = ["00"] 输出：0
提示：
rows == matrix.lengthcols == matrix[0].length0 <= row, cols <= 200matrix[i][j] 为 '0' 或 '1'注意：本题与主站 85 题相同（输入参数格式不同）： https://leetcode.cn/problems/maximal-rectangle/description/
运行时间: 48 ms
内存: 16.4 MB
class Solution:
def maximalRectangle(self, matrix: List[str]) -> int:
if not matrix: return 0
ans = 0
n = len(matrix[0])
dp = [0] * (n + 1)
for i in range(len(matrix)):
stk = []
for j in range(n + 1):
dp[j] = dp[j] + 1 if j < n and matrix[i][j] == '1' else 0
while stk and dp[stk[-1]] > dp[j]:
if (S := dp[stk.pop()] * (j - (stk[-1] + 1 if stk else 0))) > ans:
ans = S
stk.append(j)
return ans
# class Solution:
# def maximalRectangle(self, matrix: List[str]) -> int:
# if not matrix: return 0
# ans = 0
# n = len(matrix[0])
# if n == 0: return 0
# dp = [0] * (n + 1)
# for i in range(len(matrix)):
# stk = []
# for j in range(n + 1):
# dp[j] = dp[j] + 1 if j < n and matrix[i][j] == '1' else 0
# while stk and dp[stk[-1][0]] > dp[j]:
# # k = stk.pop()[0]
# # height = dp[k]
# # width = j - (stk[-1][1] + 1 if stk else 0)
# # S = height * width
# if (S:= dp[stk.pop()[0]] * (j - (stk[-1][1] + 1 if stk else 0)) )> ans:
# ans = S
# if stk and dp[j] == dp[stk[-1][0]]:
# stk[-1][1] = j
# else:
# stk.append([j,j])
# return ans
此题解使用动态规划和单调栈的组合方法。对每一行使用类似于'最大矩形'的方法，先通过动态规划更新每个位置可能达到的最大高度，这通过dp数组来记录，dp[j]存储的是直到当前行为止，第j列可以延伸的最大高度。然后对每行使用单调栈来找到以每个位置为高的最大矩形面积，更新最大值。单调栈用于维护一个高度递增的序列，从而方便地找到每个高度左边和右边第一个比它小的位置，以此计算矩形的宽度。当我们遇到比栈顶元素小的dp值时，开始计算矩形的面积并更新答案。
时间复杂度: O(mn)
空间复杂度: O(n)
# 类定义
class Solution:
# 功能：计算最大矩形的面积
def maximalRectangle(self, matrix: List[str]) -> int:
# 空矩阵处理
if not matrix: return 0
# 初始化最大面积
ans = 0
# 获取列数
n = len(matrix[0])
# dp数组初始化，多一个是为了处理边界
dp = [0] * (n + 1)
# 遍历每一行
for i in range(len(matrix)):
# 初始化栈
stk = []
# 遍历每一列
for j in range(n + 1):
# 更新dp数组
dp[j] = dp[j] + 1 if j < n and matrix[i][j] == '1' else 0
# 处理单调栈
while stk and dp[stk[-1]] > dp[j]:
# 计算可能的最大面积并更新ans
if (S := dp[stk.pop()] * (j - (stk[-1] + 1 if stk else 0))) > ans:
ans = S
# 元素索引入栈
stk.append(j)
# 返回最大面积
return ans
在动态规划中，每个位置的最大高度 `dp[j]` 代表直到当前行为止，第 j 列可以延伸的最大高度。具体更新方法是：如果当前行的第 j 个元素是 '1'，则 `dp[j]` 的值由前一行的 `dp[j]` 加 1，因为可以在前一行的高度上再增加一行；如果当前元素是 '0'，则列高度重置为 0，因为当前列不再形成连续的 '1' 序列。因此，每个 `dp[j]` 的更新依赖于同一列的前一行的 `dp[j]` 值，实现了从前一行继承并更新当前行的高度信息。
单调栈主要用于维护一个递增的高度序列，以方便计算每个高度的最大可能扩展宽度。当遇到一个当前元素（高度）比栈顶元素小的情况时，表明当前栈顶的高度无法继续向右扩展，因为遇到了一个较小的高度阻挡。此时，需要从栈中弹出栈顶元素，并计算以该高度为矩形高的最大面积。计算面积的理由是，已知这个高度左侧的边界（上一栈顶元素的位置+1），以及当前的右侧边界（当前元素的位置-1）。这样的处理直接关联到单调栈的性质，即栈中的高度始终保持递增，因此可以保证每次弹出栈顶时，计算的宽度是准确的。
公式 `S := dp[stk.pop()] * (j - (stk[-1] + 1 if stk else 0))` 用于计算以 `dp[stk.pop()]` 为高的矩形面积。其中，`dp[stk.pop()]` 是被弹出栈顶的高度，代表矩形的高度。宽度计算如下：`j` 是当前处理到的列的索引，`stk[-1]` 是栈中弹出元素后的新栈顶元素的索引，它的下一个位置即为左边界。因此，`j - (stk[-1] + 1)` 计算的是当前高度可以扩展的最大宽度（从左边界到右边界-1）。如果栈为空，则说明当前弹出的高度是到目前为止遇到的最小高度，其左边界是0，所以宽度是 `j`。这样，公式中的各部分共同确定了矩形的宽度和高度，从而计算出面积。