首页 > 其他 > 详细

leetcode(34)-柱状图中的最大矩阵

时间:2020-09-16 21:16:24      阅读:16      评论:0      收藏:0      [点我收藏+]

标签:his   pytho   rectangle   ble   一半   矩形   

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

自己的方法是优化一半的方法,使用单调栈更好

class Solution:
    def largestRectangleArea(self, heights) -> int:
        ln = len(heights)
        heights = heights[::-1]
        begins_l = [i for i in range(ln)]
        begins_r = [i for i in range(ln)]
        if ln ==0: return 0
        max_area = max(heights)
        for i,height in enumerate(heights):
            if height*ln<=max_area:
                continue
            if i > 0 and heights[i-1]>=height:
                begin_l = begins_l[i-1]
                begin_r = begins_r[i-1]
            else:
                begin_l = i
                begin_r = i
            while begin_l>0:
                if height<=heights[begin_l-1]:
                    begin_l-=1
                else:
                    break
            begins_l[i] = begin_l
            if (ln-begin_l)*height<=max_area:
                continue
            while begin_r<ln-1:
                if height<=heights[begin_r+1]:
                    begin_r+=1
                else:
                    break
            begins_r[i] = begin_r
            #print(begin_r,begin_l,max_area)
            max_area = max(max_area, (begin_r-begin_l+1)*height)
        return max_area

leetcode(34)-柱状图中的最大矩阵

标签:his   pytho   rectangle   ble   一半   矩形   

原文:https://www.cnblogs.com/Lzqayx/p/13680894.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号