Leetcode-最大矩形（单调栈）

一、题目描述

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6 解释：最大矩形如上图所示。 二、思路分析  暴力枚举+高度数组

首先我们发现，其实找一块块矩阵时，很多时候我们都要重复的寻找一些单元格，来确保我们可以找到最大的矩阵面积。 所以我们可以使用动态规划，来帮助我们记录之前查找过的矩阵信息。我们定义height[i]代表当前行的第j列往上数，数字为1的矩阵高度。然后我们开始一行行遍历，在第i行时，我们要从第j列开始往前查找j-1一直到0，每次的高度取这一路的最小值，然后不断更新最大值。

单调栈

我可以参考关于Leetcode-84.柱状图中最大的矩形。首先我们仍然计算出每一行的高度数组，然后遍历每一行，像上面这个文章一样，看成计算柱状图中的最大矩阵即可。

三、实现代码

只写了暴力枚举的，单调栈方法的代码和上个题差不多，偷个懒。

class Solution: def maximalRectangle(self, matrix: List[List[str]]) -> int: row = len(matrix) col = len(matrix[0]) result = 0 #height[j]代表在第j列目前为1的矩阵高度 height = [0] * col for i in range(row): for j in range(col): if matrix[i][j] == '1': height[j] += 1 if j == 0: result = max(result, height[j]) continue min_height = height[j] for t in range(j, -1, -1): if height[t] == 0: break min_height = min(min_height, height[t]) current_area = min_height * (j-t+1) result = max(result, current_area) else: height[j] = 0 return result