难度: Hard
给定一个仅包含 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 <= row, cols <= 200matrix[i][j] 为 '0' 或 '1'运行时间: 74 ms
内存: 22.3 MB
class Solution:
def solve(self, heights):
heights = [0] + heights + [0]
stk = []
res = 0
for i, h in enumerate(heights):
while stk and h < heights[stk[-1]]:
j = stk.pop() # height
k = stk[-1] # left bound
width = i - k - 1
res = max(res, width * heights[j])
stk.append(i)
return res
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
m = len(matrix)
n = len(matrix[0])
heights = [0] * n
ans = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
heights[j] += 1
else:
heights[j] = 0
ans = max(ans, self.solve(heights))
return ans
这个题解采用了单调栈的方法。主要思路是：逐行遍历矩阵，并维护一个高度数组 heights，heights[j] 表示第 j 列当前的连续 1 的高度。对于每一行，利用单调栈求解以当前行作为矩形底边的最大矩形面积。具体做法是，遍历高度数组，对于每个高度，利用单调栈找到左右两侧第一个小于它的位置，计算以当前高度为矩形的高、左右位置的差值为矩形的宽，求出面积并更新全局最大面积。
时间复杂度: O(m * n)
空间复杂度: O(n)
class Solution:
def solve(self, heights):
# 在高度数组首尾添加哨兵值 0，简化边界条件处理
heights = [0] + heights + [0]
stk = []
res = 0
for i, h in enumerate(heights):
while stk and h < heights[stk[-1]]:
j = stk.pop() # 当前矩形的高度
k = stk[-1] # 左边界的下标
width = i - k - 1 # 矩形的宽度
res = max(res, width * heights[j]) # 更新最大面积
stk.append(i)
return res
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
m = len(matrix)
n = len(matrix[0])
heights = [0] * n # 存储每一列的高度
ans = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == '1':
heights[j] += 1 # 如果当前位置是 1，高度加 1
else:
heights[j] = 0 # 如果当前位置是 0，高度重置为 0
ans = max(ans, self.solve(heights)) # 求解以当前行为底的最大矩形面积
return ans
在单调栈的应用中，我们确保栈内元素保持单调递增的顺序。当遇到一个新的高度`h`小于栈顶元素高度时，表示找到了栈顶元素的右边界。因此，我们不断弹出栈顶元素，直到栈顶元素的高度小于或等于当前高度`h`。这样操作保证了栈中仅保留那些还未找到右边界的高度的下标，且每个元素只会被处理一次，保证了高效性。
添加哨兵值0到高度数组的首尾主要是为了简化边界条件的处理。首先，在数组的开始添加0可以保证栈内总是有元素，方便处理左边界。在数组末尾添加0则是为了在最后一次循环中清空栈，保证所有的高度都能找到右边界并计算面积。这避免了在循环结束后还需额外的逻辑来清空栈中的元素。
将遇到的'0'的高度重置为0是必要的，因为如果某个位置的值是'0'，那么任何包含这个位置的矩形都不能被视为全1的矩形。这种做法实际上是在正确地更新每列的'连续1的高度'。它不会忽略潜在的最大矩形，因为每一行都会基于当前的高度数组求解最大矩形，确保考虑了所有可能的矩形。
在函数`solve`中，`i`指的是当前考虑的高度的下标，而`k`是栈顶元素的下标，即当前高度左侧第一个小于当前高度的位置的下标。当从栈中弹出一个元素`j`时（即当前考虑的矩形的高度），栈顶的新元素`k`就成为了这个高度的新的左边界。因此，`i - k - 1`计算的是从左边界`k`到当前位置`i`之间的距离，减去1是因为左边界本身不包含在内，这样就得到了矩形的宽度。