题解 | #单调栈结构#

本题解使用从栈顶到栈底单调递减的栈。

遍历整个数组的索引，若栈为空，则将该索引放入栈里，若栈不为空，则比较栈顶索引对应的值与当前遍历到的索引对应的值。

1、若栈顶索引对应的值较小，则继续将当前遍历到的索引放入栈中

2、若栈顶索引对应的值较大，则将该索引从栈顶弹出。

_ = input()
nums = list(map(int, input().split()))

stack = []
ans = [[-1, -1] for _ in range(len(nums))]

for i in range(len(nums)):
    while stack and nums[stack[-1]] > nums[i]:
        ans[stack[-1]][1] = i
        stack.pop()
    if stack:
        if nums[stack[-1]] < nums[i]:
            ans[i][0] = stack[-1]
        elif nums[stack[-1]] == nums[i]:
            ans[i][0] = ans[stack[-1]][0]
    stack.append(i)

for i, j in ans:
    print(i, j)