【LeetCode日记】85. 最大矩形

  • 2020 年 3 月 12 日
  • 筆記

题目描述

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

示例:

输入:

[    ["1","0","1","0","0"],    ["1","0","1","1","1"],    ["1","1","1","1","1"],    ["1","0","0","1","0"]  ]

输出: 6

思路

我在 【84. 柱状图中最大的矩形】多种方法（Python3）[1] 使用了多种方法来解决。然而在这道题，我们仍然可以使用完全一样的思路去完成。不熟悉的可以看下我的题解。本题解是基于那道题的题解来进行的。

拿题目给的例子来说：

[    ["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

复杂度分析

  • 时间复杂度：
  • 空间复杂度：

参考资料

[1]

【84. 柱状图中最大的矩形】多种方法（Python3）: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-zhu-zhuang-tu-zhong-zui-da-de-ju-xing-duo-chong/

VirMach 便宜 VPS

QNews

QNews