最大矩形

题目描述
给定一个仅包含0和1的二维二进制矩阵，找到只包含1的最大矩形，并返回其面积。

示例
输入：
matrix = [
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出：6
解释：最大矩形如右图所示，面积为6。

解题过程

这个问题可以通过将二维问题分解为多个一维问题来解决。核心思路是：对于矩阵的每一行，我们可以计算一个高度数组，然后在这个高度数组上应用"柱状图中最大矩形"的算法。

步骤1：预处理高度数组
对于每一行，我们维护一个高度数组heights，其中heights[j]表示从当前行向上连续1的个数（包括当前行）。

以示例为例：

• 第0行：[1,0,1,0,0]
• 第1行：[2,0,2,1,1]（第二行的每个位置，如果是1，就加上上一行对应位置的高度）
• 第2行：[3,1,3,2,2]
• 第3行：[4,0,0,3,0]

步骤2：对每行应用柱状图最大矩形算法
对于每一行的heights数组，我们需要找到最大的矩形面积。这可以通过单调栈来解决。

单调栈算法的具体步骤：

1. 初始化一个空栈，用于存储柱子的索引
2. 遍历每个柱子：
   • 当栈不为空且当前柱子的高度小于栈顶柱子的高度时，弹出栈顶柱子并计算面积
   • 将当前柱子索引入栈
3. 处理栈中剩余的柱子

步骤3：面积计算细节
对于每个弹出的柱子，我们计算以该柱子高度为矩形高度的最大面积：

• 宽度 = 当前索引 - 栈顶索引 - 1（如果栈为空，则宽度就是当前索引）
• 面积 = 高度 × 宽度

具体实现

def maximalRectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    
    rows, cols = len(matrix), len(matrix[0])
    heights = [0] * cols
    max_area = 0
    
    for i in range(rows):
        # 更新高度数组
        for j in range(cols):
            if matrix[i][j] == '1':
                heights[j] += 1
            else:
                heights[j] = 0
        
        # 计算当前行的最大矩形面积
        stack = []
        for j in range(cols + 1):
            # 添加一个虚拟的柱子高度-1，确保栈中所有柱子都被处理
            current_height = heights[j] if j < cols else -1
            
            while stack and current_height < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = j if not stack else j - stack[-1] - 1
                max_area = max(max_area, height * width)
            
            stack.append(j)
    
    return max_area

复杂度分析

• 时间复杂度：O(m×n)，其中m是行数，n是列数
• 空间复杂度：O(n)，用于存储高度数组和栈

这个算法通过将二维问题转化为多个一维问题，巧妙地利用单调栈来高效求解最大矩形面积。