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