leetcode-85 最大矩形
发布时间:2020-12-20 12:59:46 所属栏目:Python 来源:网络整理
导读:leetcode-85 最大矩形 题目描述: 给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 注:用leetode-84题的思路,每一行都做一次最大矩形,挺有趣 import numpy as npclass Solution: def maximalRectangle(self,matrix: Li
leetcode-85 最大矩形题目描述:
import numpy as np class Solution: def maximalRectangle(self,matrix: List[List[str]]) -> int: if not matrix: return 0 row,col = len(matrix),len(matrix[0]) height = [0] * col res = 0 for r in matrix: for i in range(col): if r[i] == '0': height[i] = 0 else: height[i] += 1 res = max(res,self.findLarge(height)) return res def findLarge(self,heights): stack = list() res = 0 heights.append(0) N = len(heights) for i in range(N): if not stack or heights[i]>heights[stack[-1]]: stack.append(i) else: while stack and heights[i] <= heights[stack[-1]]: h = heights[stack.pop()] w = i if not stack else i - stack[-1] - 1 res = max(res,h*w) stack.append(i) return res (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |