LeetCode85最大矩形

发表于 | 更新于 | 分类于 |
本问题可以进行转换，转换成84题的解题思路

题目描述

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

示例:

1
2
3
4
5
6
7
8
输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

解题思路

思路一：暴力法

一行一行的遍历数组，维护每个位置到顶部的高度，如果某位置高度大于0，就往回扫描到首列，同时维护一个当前最低的高度，这样就可以求出从这个位置到第一列的最大面积了。时间复杂度是$O(mn^2)$，当然通过转置可以优化到$O(mn min(m, n))$，但数量级不变。

思路二：动态规划法

由于在暴力枚举法中我们每碰到一个高度不为0的情况就往左搜索找到当前最低的高度然后更新面积，所以会导致重复计算。动态规划刚好可以通过记录原有信息来避免重复搜索。那么每一行我们需要记录什么呢？我们需要记录并维护的就是一行中每个位置高度的左右边界。

思路三：递增栈法

主要是分为两步，第一步是将原始输入做一下映射。

对每一行做转换，本例中原始输入可转换为：

1
2
3
4
5
6
[
  ["1","0","1","0","0"],
  ["2","0","2","1","1"],
  ["3","1","3","2","2"],
  ["4","0","0","3","0"]
]

每个元素的值 = 该值按列向上遍历，遇到非0元素的个数和（包含自身）

然后对每一行输入使用第84题中的解题方法求出最大矩形，最后求所有行的最大矩形面积即可。