python实现leetcode之84. 柱状图中最大的矩形

解题思路

找出最低点
如果最高点==最低点，就是一个矩形，直接计算面积即可
否则，那些最低的点将区间分成若干互补相连的字区间，字区间的每个点都比原最低点高

递归考察每一个区间，然后计算找出他们的最大值

84. 柱状图中最大的矩形

代码

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        return largest_area(heights, 0, len(heights))


def largest_area(arr, low, high):
    if low >= high: return 0
    if low + 1 == high: return arr[low]
    mi_idx = mx_idx = low
    for idx in range(low, high):
        if arr[idx] < arr[mi_idx]:
            # 找到最低高度的第一个下标
            mi_idx = idx
        if arr[idx] > arr[mx_idx]:
            # 找到最高高度的第一个下标
            mx_idx = idx
    
    if mi_idx == mx_idx:
        return arr[mi_idx] * (high-low)  # 高低一样，面积就是宽*高

    begin = None
    zones = []
    # 最低的那些点将区域分成几个都比他高的点，然后分别考察
    for idx in range(low, high):
        if arr[idx] > arr[mi_idx]:
            if begin is None:
                begin = idx
        if arr[idx] == arr[mi_idx]:
            if begin is not None:
                zones.append((begin, idx))
                begin = None
    if begin is not None:
        zones.append((begin, high))

    rtv = arr[mi_idx] * (high-low)
    for x, y in zones:
        rtv = max(rtv, largest_area(arr, x, y))
    return rtv