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

标签：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