柱状图中的最大矩形（python）

思路单调递增栈遍历数组入栈索引。首先设置两个高度为0的柱子作为哨兵前后各设置一个。使用一个单调递增栈当栈不为空且当前元素大于栈顶元素时入栈。若当前元素小于栈顶元素时说明找到了第一个比栈顶元素矮的元素弹出一个栈顶元素此时的栈顶元素就是左边界L此时遍历到的元素就是右边界R先前被弹出的元素就是高度Hheights[i]则此时矩阵面积为AreaH*(L-R-1)#柱状图中的最大矩形 import sys from typing import List def largestRectangleArea(h:List[int])-str: maxArea0 stack[] for i in range(len(h)): while stack and h[i]h[stack[-1]]: #当前元素大于小于栈顶元素 tmpstack.pop() #出栈 ah[tmp] #柱子高度 bi-stack[-1]-1 #柱子宽度i是右边界stack[-1]是左边界 maxAreamax(maxArea,a*b) stack.append(i) return maxArea def main(): linesys.stdin.readline().strip() if not line: return 0 heightslist(map(int,line.split())) #转换成数组 h[0]heights[0] #前后拼接两个高度为0的柱子 reslargestRectangleArea(h) print(res) return if __name____main__: main()