题目描述与示例
一贫如洗的椎夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从 0-N 的子，每个箱子上面有一个数字，箱子排列成一个环，编号最大的箱子的下一个是编号为 0 的箱子。请输出每个箱子贴的数字之后的第一个比它大的数，如果不存在则输出-1。
输入
输入一个数字字串，数字之间使用逗号分隔，例如: 1,2,3,1；1 ≤ 字串中数字个数 ≤ 10000；-100000≤ 每个数字值 ≤100000
输出
下一个大的数列表，以逗号分隔，例如: 2,3,6,-1,6
示例一
输入
2,5,2
输出
5,-1,5
说明
第一个 2 的下一个更大的数是 5
数字 5 找不到下一个更大的数
第二个 2 的下一个最大的数需要循环搜索，结果也是 5
示例二
输入
3,4,5,6,3
输出
4,5,6,-1,4
解题思路
注意，本题和LC503. 下一个更大元素II完全一致。
寻找下一个更大元素，看到这个字眼应该马上想到单调栈解法。本题的难点在于处理环型数组。
我们仅需在遍历一次数组之后，再次遍历数组，即可以模拟环型数组。因此我们可以用以下代码来遍历数组
# 正序遍历
for i in range(2*n):
idx = i % n
# 逆序遍历
for i in range(2*n-1, -1, -1):
idx = i % n
其中n是原数组nums的长度，idx = i % n是元素在原数组nums和答案数组ans中的索引。
除此之外，在更新答案的过程中，还需要再判断ans[idx]是否为-1，如果不是-1，则说明之前已经更新过了，无需重复更新。
剩下部分和常规的单调栈题目没有任何区别。
代码
解法一
正序遍历nums构建单调栈。
# 题目：2023B-阿里巴巴找黄金宝箱(4)
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：单调栈-正序遍历原数组
# 代码看不懂的地方，请直接在群上提问
nums = list(map(int, input().split(",")))
n = len(nums)
stack = list()
ans = [-1] * n
for i in range(2*n):
idx = i % n
num = nums[idx]
while(stack and nums[stack[-1]] < num):
top_idx = stack.pop()
ans[top_idx] = num
stack.append(idx)
print(",".join(map(str, ans)))
解法二
逆序遍历nums构建单调栈。
# 题目：2023B-阿里巴巴找黄金宝箱(4)
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：单调栈-逆序遍历原数组
# 代码看不懂的地方，请直接在群上提问
nums = list(map(int, input().split(",")))
n = len(nums)
stack = list()
ans = [-1] * n
for i in range(2*n-1, -1, -1):
idx = i % n
num = nums[idx]
while(stack and nums[stack[-1]] <= num):
stack.pop()
if stack:
ans[idx] = nums[stack[-1]]
stack.append(idx)
print(",".join(map(str, ans)))
时空复杂度
时间复杂度：O(N)。仅需两次遍历数组nums，O(2N) = O(N)。
空间复杂度：O(N)。单调栈所占用的额外空间。
N为原数组nums的长度。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
