AcWing 131. 直方图中最大的矩形
原题链接
简单
作者:
Re_31
,
2024-03-24 11:42:33
,
所有人可见
,
阅读 7
def findS(nums,flag):
n=len(nums)
stk=[]
res=[0 for i in range(n)]
if flag==1:
for i in range(n):
while len(stk)>0 and nums[stk[-1]]>=nums[i]:
stk.pop()
if len(stk)==0:
res[i]=-1
else:
res[i]=stk[-1]
stk.append(i)
else:
for i in range(n-1,-1,-1):
while len(stk)>0 and nums[stk[-1]]>=nums[i]:
stk.pop()
if len(stk)==0:
res[i]=n
else:
res[i]=stk[-1]
stk.append(i)
return res
while 1:
nums=[int(num)for num in input().split()]
if len(nums)!=1:
nums=nums[1:]
n=len(nums)
res1=findS(nums,1)
res2=findS(nums,0)
maxS=0
for i in range(n):
maxS=max(maxS,(res2[i]-res1[i]-1)*nums[i])
print(maxS)
else:
break