单调栈

一个单调递增的栈，栈内数据形成的矩形面积为

最低值（栈首）x总长度

但是输入不可能是单调递增的，因此要维持单调性，当后续值无法再入栈时必须将末尾较大的值出栈，直到新的数可以入栈。

出栈的数计算其形成的面积（高度x累积的宽度），并把出栈的个数累积为宽度，作为新入栈的数所携带的宽度数据。

每次计算面积，都更新最大面积。

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param heights int整型一维数组 
# @return int整型
#
    
    
def walk2(heights):#单调栈思路
    if len(heights)==0:#空列表直接返回0
        return 0
    width=[1 for _ in range(len(heights))]#记录每个位置累积的宽度，初始都为1
    stack=[0]#单调栈，记录下标
    maxSize=0#最大面积
    for i in range(1,len(heights)):
        if heights[i]>heights[stack[-1]]:#单调递增入栈
            stack.append(i)
        else:
            wide=0
            while len(stack)>0:#否则末尾出栈，直到当前值可以符合单调递增入栈条件
                last=stack.pop()
                wide+=width[last]#累加已经出栈的宽度
                maxSize=max(heights[last]*wide,maxSize)#每次出栈，计算以该出栈数为高形成的矩形面积，并更新最大面积
                if len(stack)==0 or heights[stack[-1]]<heights[i]:#找到可入栈位置或栈已经清空
                    break
            stack.append(i)#当前值入栈
            width[i]+=wide#当前值累积前面的宽度
    wide=0
    while len(stack)>0:#遍历完毕后，清理剩余在栈中的数
        last=stack.pop()
        wide+=width[last]
        maxSize=max(heights[last]*wide,maxSize)
    return maxSize
                
        
class Solution:
    def largestRectangleArea(self , heights: List[int]) -> int:
        maxSize=walk2(heights)
        return maxSize