AcWing 131. 直方图中最大的矩形
原题链接
简单
作者:
Scat
,
2024-03-24 14:37:50
,
所有人可见
,
阅读 3
while True:
s = list(map(int, input().split()))
if s[0] == 0:
break
nums = [-1] + s[1:] + [-1]
queue = []
l = [0 for i in range(s[0] + 1)]
r = [0 for i in range(s[0] + 1)]
queue.append(0)
for i in range(1, s[0] + 1):
while queue and nums[queue[-1]] >= nums[i]:
queue.pop()
l[i] = queue[-1]
queue.append(i)
queue.clear()
queue.append(s[0] + 1)
for i in range(s[0], 0, -1):
while queue and nums[queue[-1]] >= nums[i]:
queue.pop()
r[i] = queue[-1]
queue.append(i)
res = 0
for i in range(1, s[0] + 1):
res = max(res, (r[i] - l[i] - 1) * nums[i])
print(res)