编程面试：用单调栈解决循环数组的下一个更大元素
面试官考察点
给定循环整数数组，返回每个元素沿顺时针方向遇到的第一个严格更大元素；不存在时返回 -1。数组可能包含重复值、单调序列和全部相同的值。
约束与边界
- 结果必须是严格更大，等值不能出栈并成为答案。
- 循环意味着下标
i的候选顺序为i+1到n-1，再回到0。 - 每个位置最多需要一个答案，不能因为第二趟扫描覆盖已确定结果。
- 目标是 O(n) 时间和 O(n) 空间。
30 秒回答框架
“我维护一个按值递减的索引栈，栈中元素还没有找到更大值。扫描虚拟的两倍数组：当前值严格大于栈顶时持续弹出并填答案；第一趟把所有位置入栈，第二趟只为未解决位置提供环回候选。每个索引最多入栈一次、出栈一次，复杂度 O(n)。”
让栈保存等待答案的位置
栈保存索引而不是值，便于写回结果并保留重复值的相对位置。维持从栈底到栈顶的非递增值序；遇到更大值时，所有被它解决的索引都可以弹出。
把环回变成有限扫描
把访问位置写成 i % n，让 i 从 0 扫到 2n-2。第一次遇到某索引时先入栈；第二次遇到同一索引时只用于解决栈中等待者，不再重复入栈。这样不会真的复制数组，也不会无限循环。
严格大于与重复值
弹出条件必须是 nums[current] > nums[stackTop]。使用大于等于会让相同值错误地互相解决；使用小于则会破坏递减栈不变量。不存在更大值的索引在扫描结束后保留 -1。
回答前需要澄清的问题
- “下一个”是否严格大于？若改为大于或等于，弹出条件和重复值答案都会改变。
- 数组是否允许空？空数组的返回形式要提前定义。
- 需要返回值还是下标？若返回距离或下标，结果结构和环回计算会不同。
分步骤深入解答
初始化结果为 -1，栈为空。对于虚拟位置 i，令 index = i % n，读取 value = nums[index]。先用 value 解决所有栈顶较小的索引；当 i 小于 n 时，把 index 入栈，表示它仍等待右侧更大值。第二趟不会再次入栈，因此每个索引只加入一次。
result = [-1] * n
stack = []
for i in range(2 * n - 1):
index = i % n
while stack and nums[stack[-1]] < nums[index]:
result[stack.pop()] = nums[index]
if i < n:
stack.append(index)例如 [1,2,1] 的第二个 1 会在环回时看到 2，而 2 自己没有严格更大的值。扫描结束后栈中索引对应 -1，不需要额外清理。
高质量示范回答
“我用索引栈保存尚未找到答案的位置，并保持栈底到栈顶的值非递增。把数组逻辑上扫描两遍，每次用 i % n 读取元素；当前值严格大于栈顶时就弹出并写答案。第一遍遇到位置才入栈，第二遍只做环回匹配，避免重复入栈。结果先填 -1，因此全相同数组和无更大值位置自然正确。每个索引最多入栈、出栈一次，时间 O(n)，空间 O(n)。”
常见错误
- 为了处理循环而复制三倍数组，增加不必要的空间和边界风险。
- 第二趟再次入栈，导致同一索引被处理多次或答案被覆盖。
- 使用大于等于处理重复值，让相同元素被误判为更大。
- 从右向左扫描却没有明确栈不变量，导致答案不是第一个更大值。
- 没有先填
-1，结束后为栈中索引补答案时出现未初始化值。
错误表现与修正
对 [1,1,1] 返回非 -1 的值，说明等值条件错误；对 [1,2,1] 第三个位置返回 -1，说明没有进行环回扫描。修正时逐步打印栈索引和值，并断言每次弹出前当前值严格更大。
生产化实现
将结果和栈使用足够宽的索引类型；若输入规模可能接近内存上限，避免复制数组。需要返回距离时，在弹出索引 j 时计算 (index - j + n) % n，并规定是否允许距离为零。
验证清单
覆盖空数组、单元素、全相同、严格递增、严格递减、重复峰值和随机数组。小规模输入用 O(n²) 参考实现逐位置向前查找，进行随机对拍，验证值、顺序与 -1 边界。
追问及应对
为什么每个索引最多弹出一次？
索引一旦找到严格更大的值就离开栈；之后更远的元素不可能成为它的“第一个”更大值。每次入栈一次、出栈一次，所以总弹出次数是 O(n)。
如果要求下一个大于或等于的元素呢？
把弹出条件改为小于或等于，并重新确认重复元素的顺序。等值元素会互相解决，题目通常还要明确是否允许返回自身在环上的再次出现。
如果数组改为无限重复流呢？
不能等待所有位置都有答案；需要给出有限观察窗口或超时策略。对固定数组，最多扫描两遍已经覆盖每个位置后续的所有候选。
评分标准
- 状态不变量：说明递减栈保存等待答案的索引。
- 环回处理：使用两趟或等价有限扫描，不复制或无限循环。
- 重复值边界：严格使用大于条件，并保留无答案为
-1。 - 复杂度准确：O(n) 时间、O(n) 额外空间。
- 验证充分：包含 O(n²) 参考实现和随机、重复、单调序列测试。
合规检查
确认栈不变量、环回边界和复杂度结论在回答中保持一致。
面试作答要点
先讲“栈中索引等待更大值”，再说明 i % n 的两趟扫描、严格大于的弹出条件和只入栈一次，最后给出摊还复杂度。
一句话总结
循环数组的下一个更大元素可以通过两趟索引扫描和单调递减栈在线性时间内完成，重复值与无答案位置由严格比较和 -1 初始化保证。