leetcode-84 柱状图中的最大矩形
发布时间:2020-12-20 12:59:50 所属栏目:Python 来源:网络整理
导读:leetcode-84 柱状图中的最大矩形 参考:负雪明烛 题目描述: 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积 感觉脑袋不够用,关键是找到右边界和左边界; class Soluti
leetcode-84 柱状图中的最大矩形参考:负雪明烛
class Solution: def largestRectangleArea(self,heights: List[int]) -> int: 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的计算 w = i if not stack else i - stack[-1] - 1 res = max(res,h*w) stack.append(i) return res (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |