0085. 最大矩形
题目地址（85. 最大矩形）
题目描述
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例：
输入：
1
[
2
["1","0","1","0","0"],
3
["1","0","1","1","1"],
4
["1","1","1","1","1"],
5
["1","0","0","1","0"]
6
]
Copied!
输出：6
前置知识
- 单调栈
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
我在 【84. 柱状图中最大的矩形】多种方法（Python3） 使用了多种方法来解决。 然而在这道题，我们仍然可以使用完全一样的思路去完成。 不熟悉的可以看下我的题解。本题解是基于那道题的题解来进行的。
拿题目给的例子来说：
1
[
2
["1","0","1","0","0"],
3
["1","0","1","1","1"],
4
["1","1","1","1","1"],
5
["1","0","0","1","0"]
6
]
Copied!
我们逐行扫描得到
84. 柱状图中最大的矩形 中的 heights 数组：
这样我们就可以使用
84. 柱状图中最大的矩形 中的解法来进行了，这里我们使用单调栈来解。下面的代码直接将 84 题的代码封装成 API 调用了。
代码
代码支持：Python
Python Code:
1
class Solution:
2
def largestRectangleArea(self, heights: List[int]) -> int:
3
n, heights, st, ans = len(heights), [0] + heights + [0], [], 0
4
for i in range(n + 2):
5
while st and heights[st[-1]] > heights[i]:
6
ans = max(ans, heights[st.pop(-1)] * (i - st[-1] - 1))
7
st.append(i)
8
9
return ans
10
def maximalRectangle(self, matrix: List[List[str]]) -> int:
11
m = len(matrix)
12
if m == 0: return 0
13
n = len(matrix[0])
14
heights = [0] * n
15
ans = 0
16
for i in range(m):
17
for j in range(n):
18
if matrix[i][j] == "0":
19
heights[j] = 0
20
else:
21
heights[j] += 1
22
ans = max(ans, self.largestRectangleArea(heights))
23
return ans
Copied!
复杂度分析
- 时间复杂度：$O(M * N)$
- 空间复杂度：$O(N)$
相关题目
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 38K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最近更新 1yr ago