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

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

 



以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

 



图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

 

示例:

输入: [2,1,5,6,2,3]
输出: 10

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from typing import *


def largestRectangleArea(height: List[int]) -> int:
    height.append(0)
    height.insert(0, 0)
    height_index = [(height[i], i) for i in range(len(height))]

    left_stack, right_stack = [], []
    left_area, right_area, area = [0 for _ in range(len(height))], [0 for _ in range(len(height))], []
    for i in range(len(height)):
        cur = height_index[i]
        if len(right_stack) == 0 or cur[0] >= right_stack[-1][0]:
            right_stack.append(cur)
        else:
            while len(right_stack) > 0 and right_stack[-1][0] > cur[0]:
                tmp = right_stack.pop()
                right_area[tmp[1]] = tmp[0] * (cur[1] - tmp[1] - 1)
            right_stack.append(cur)

    for i in range(len(height) - 1, -1, -1):
        cur = height_index[i]
        if len(left_stack) == 0 or cur[0] >= left_stack[-1][0]:
            left_stack.append(cur)
        else:
            while len(left_stack) > 0 and left_stack[-1][0] > cur[0]:
                tmp = left_stack.pop()
                left_area[tmp[1]] = tmp[0] * (tmp[1] - cur[1] - 1)
            left_stack.append(cur)

    for i in range(len(height)):
        area.append(left_area[i] + right_area[i] + height[i])

    return max(area)


if __name__ == '__main__':
    print(largestRectangleArea([2,1,5,6,2,3]))
