题目描述
给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出:6
难度:Middle
前置知识
- 单调栈
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
我在 【84. 柱状图中最大的矩形】多种方法(Python3) 使用了多种方法来解决。 然而在这道题,我们仍然可以使用完全一样的思路去完成。 不熟悉的可以看下我的题解。本题解是基于那道题的题解来进行的。
拿题目给的例子来说:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
我们逐行扫描得到 84. 柱状图中最大的矩形
中的 heights 数组:
这样我们就可以使用84. 柱状图中最大的矩形
中的解法来进行了,这里我们使用单调栈来解。
代码
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n, heights, st, ans = len(heights), [0] + heights + [0], [], 0
for i in range(n + 2):
while st and heights[st[-1]] > heights[i]:
ans = max(ans, heights[st.pop(-1)] * (i - st[-1] - 1))
st.append(i)
return ans
def maximalRectangle(self, matrix: List[List[str]]) -> int:
m = len(matrix)
if m == 0: return 0
n = len(matrix[0])
heights = [0] * n
ans = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == "0":
heights[j] = 0
else:
heights[j] += 1
ans = max(ans, self.largestRectangleArea(heights))
return ans
复杂度分析
- 时间复杂度:$O(M * N)$
- 空间复杂度:$O(N)$
-
原题leetcode链接:https://leetcode-cn.com/problems/maximal-rectangle/
更多题解可以访问我的 前端中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com