AcWing 830. 单调栈
原题链接
简单
作者:
邓学士
,
2024-04-13 00:00:18
,
所有人可见
,
阅读 1
思路
单调栈的基本思想是从原数列中挑选出形成(单调减|增)的数列栈
#对于本题而言,我们建立的单调栈是stack。
1. 我使用了一个栈来存储整数数列,对于每个数,如果栈为空则将当前数的下标入栈
2. 对于栈不为空的情况,我对于当前的数于栈顶元素进行了对比:
1:如果当前数小于栈顶元素所对应的数值,则说明找到了原数列中左边第一个比它小的数,将栈顶元素出栈。并将栈顶元素赋值给result[i]
2:对于当前数大于栈顶元素所对应的数值则直接使下标入栈
3. 最后result中包含的就是我们想要的答案
代码
N = int(input())
nums = list(map(int, input().split()))
stack = []
result = [-1] * N
for i in range(N):
# 当栈不为空,且栈顶元素大于当前元素时
# 弹出当前元素下标
while stack and nums[stack[-1]]>=nums[i]:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
print(*result)