作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
输入格式
- matrix：二维字符数组，其中 ‘1’ 和 ‘0’ 分别表示有和无。
输出格式
- 返回最大矩形的面积。
示例
示例 1
输入: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] 输出: 6
方法一：动态规划 - 按行计算高度
解题步骤
- 构建高度数组：将每一行视为底，构建当前行为底的直方图。
- 直方图最大矩形：使用单调栈找出每个直方图的最大矩形面积。
完整的规范代码
def maximalRectangle(matrix): """ 动态规划计算基于直方图的最大矩形面积 :param matrix: List[List[str]], 二维二进制矩阵 :return: int, 最大矩形的面积 """ if not matrix or not matrix[0]: return 0 max_area = 0 n = len(matrix[0]) height = [0] * (n + 1) # 额外的一个0作为哨兵，简化代码 for row in matrix: for i in range(n): height[i] = height[i] + 1 if row[i] == '1' else 0 # 单调栈计算最大矩形面积 stack = [] for i in range(n + 1): while stack and height[i] < height[stack[-1]]: h = height[stack.pop()] w = i if not stack else i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area # 示例调用 print(maximalRectangle([["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]])) # 输出: 6
算法分析
- 时间复杂度：(O(M * N))，其中 (M) 和 (N) 分别是矩阵的行数和列数。
- 空间复杂度：(O(N))，用于存储高度数组和栈的空间。
方法二：动态规划 - 优化的行处理
解题步骤
- 计算三个数组：
left，right和height数组。
left[i]表示第i列的连续1最左能达到的边界。right[i]表示第i列的连续1最右能达到的边界。height[i]表示第i列的连续1的高度。
- 更新和计算面积：在更新这三个数组的同时，计算可能的最大矩形面积。
完整的规范代码
def maximalRectangle(matrix): """ 动态规划优化的行处理计算最大矩形面积 :param matrix: List[List[str]], 二维二进制矩阵 :return: int, 最大矩形的面积 """ if not matrix or not matrix[0]: return 0 max_area = 0 n = len(matrix[0]) height = [0] * n left = [0] * n right = [n] * n for row in matrix: cur_left, cur_right = 0, n # 更新左边界 for i in range(n): if row[i] == '1': left[i] = max(left[i], cur_left) else: left[i] = 0 cur_left = i + 1 # 更新右边界 for i in range(n-1, -1, -1): if row[i] == '1': right[i] = min(right[i], cur_right) else: right[i] = n cur_right = i # 更新高度和计算面积 for i in range(n): if row[i] == '1': height[i] += 1 max_area = max(max_area, (right[i] - left[i]) * height[i]) else: height[i] = 0 return max_area # 示例调用 print(maximalRectangle([["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]])) # 输出: 6
算法分析
- 时间复杂度：(O(M * N))，每个元素处理一次。
- 空间复杂度：(O(N))，用于存储
left、right和height数组。
方法三：最大矩形转化为最大直方图问题
解题步骤
- 转化问题：将每一行看作直方图的底部，通过累积将二维问题转换为一系列一维直方图问题。
- 应用单调栈：对每个生成的直方图使用单调栈方法计算最大矩形面积。
完整的规范代码
def maximalRectangle(matrix): """ 转化为直方图处理每行的最大矩形面积 :param matrix: List[List[str]], 二维二进制矩阵 :return: int, 最大矩形的面积 """ if not matrix: return 0 max_area = 0 n = len(matrix[0]) height = [0] * (n + 1) for row in matrix: for i in range(n): height[i] = height[i] + 1 if row[i] == '1' else 0 stack = [-1] for i in range(n + 1): while height[i] < height[stack[-1]]: h = height[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area # 示例调用 print(maximalRectangle([["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]])) # 输出: 6
算法分析
- 时间复杂度：(O(M * N))，其中 (M) 和 (N) 分别是矩阵的行数和列数。每个元素最多进出栈一次。
- 空间复杂度：(O(N))，用于存储高度和栈的空间。
方法四：改进的动态规划
解题步骤
- 建立模型：类似于方法二，使用动态规划，但这次只用两个数组交替更新，减少空间复杂度。
- 连续更新：使用两个数组
current_left和current_right交替更新，以优化空间使用。
完整的规范代码
def maximalRectangle(matrix): """ 改进的动态规划算法，优化空间复杂度 :param matrix: List[List[str]], 二维二进制矩阵 :return: int, 最大矩形的面积 """ if not matrix or not matrix[0]: return 0 max_area = 0 n = len(matrix[0]) height = [0] * n current_left = [0] * n current_right = [n] * n for row in matrix: left, right = 0, n # 更新左边界 for i in range(n): if row[i] == '1': current_left[i] = max(current_left[i], left) else: current_left[i] = 0 left = i + 1 # 更新右边界 for i in range(n - 1, -1, -1): if row[i] == '1': current_right[i] = min(current_right[i], right) else: current_right[i] = n right = i # 更新高度和计算面积 for i in range(n): if row[i] == '1': height[i] += 1 max_area = max(max_area, (current_right[i] - current_left[i]) * height[i]) else: height[i] = 0 return max_area # 示例调用 print(maximalRectangle([["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]])) # 输出: 6
算法分析
- 时间复杂度：(O(M * N))，每个元素被处理一次。
- 空间复杂度：(O(N))，使用了三个数组来存储当前行的状态。
方法五：基于位操作的优化
解题步骤
- 位操作：将每一行看作一个二进制数，通过位操作合并行，求连续行的公共 ‘1’ 部分。
- 求连续最大行数：计算每一列连续 ‘1’ 的最大数量，进而计算最大面积。
完整的规范代码
def maximalRectangle(matrix): """ 基于位操作的优化算法，处理连续行的公共部分 :param matrix: List[List[str]], 二维二进制矩阵 :return: int, 最大矩形的面积 """ if not matrix: return 0 m, n = len(matrix), len(matrix[0]) heights = [0] * n max_area = 0 for i in range(m): for j in range(n): # 更新高度 if matrix[i][j] == '1': heights[j] += 1 else: heights[j] = 0 # 使用单调栈找最大矩形面积 stack = [-1] for j in range(n + 1): while stack and (j == n or heights[stack[-1]] > heights[j]): h = heights[stack.pop()] w = j if stack[-1] == -1 else j - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(j) return max_area # 示例调用 print(maximalRectangle([["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]])) # 输出: 6
算法分析
- 时间复杂度：(O(M * N))，每行使用单调栈算法处理。
- 空间复杂度：(O(N))，使用栈和高度数组存储信息。
不同算法的优劣势对比
| 特征 | 方法一：动态规划 | 方法二：单调栈 | 方法三：分治法 | 方法四：改进动态规划 | 方法五：位操作优化 |
| 时间复杂度 | (O(M * N)) | (O(M * N)) | 平均 (O(M * N)), 最坏 (O(M * N^2)) | (O(M * N)) | (O(M * N)) |
| 空间复杂度 | (O(N)) | (O(N)) | (O(N)) | (O(N)) | (O(N)) |
| 优势 | 易于理解和实现 | 高效，通常用于解决此类问题 | 适用于某些特殊情况 | 空间优化 | 高效，适用于行数较多的情况 |
| 劣势 | 空间消耗较大 | 需要理解单调栈 | 较为复杂，不易实现 | 复杂度略高 | 需要位操作的理解和实现 |
应用示例
这些方法在计算几何、图形渲染、图像处理、资源分配和数据分析中非常有用，特别是在需要优化和处理大规模数据集的情况下。
欢迎关注微信公众号 数据分析螺丝钉
