题目要求
给定一个循环整数数组 nums，返回数组 answer。
对每个下标 i：
answer[i] = 从 i 向右遇到的第一个严格大于 nums[i] 的元素值
如果绕行一圈后仍然没有更大元素，answer[i] = -1。
“循环数组”表示走过最后一个位置后，可以继续从下标 0 开始；但一个下标不能绕一圈后把自己当成答案。
LeetCode 提供的方法接口是：
nextGreaterElements(nums: List[int]) -> List[int]
示例 1
输入：nums = [1,2,1]
输出：[2,-1,2]
- 第一个
1向右首先遇到更大的2。 2绕行一圈也找不到严格更大的元素，答案是-1。- 最后一个
1走到数组末尾后绕回开头，随后遇到2。
示例 2
输入：nums = [2,2,2]
输出：[-1,-1,-1]
相等元素不属于“更大元素”。
示例 3
输入：nums = [7]
输出：[-1]
数组只有一个元素时，它不能把自己作为下一个更大元素。
约束
1 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9
Step 1：循环数组中的“右边”到哪里结束
先看：
nums = [1,2,1]
如果这是普通数组，最后一个 1 的右侧已经没有元素。但题目说数组是循环的，所以它接下来的观察顺序是：
数组开头的 1
-> 中间的 2
遇到 2 时，才找到第一个严格更大的值。
当前 baseline 是：
从当前位置向右观察；到达末尾后从开头继续。
这个 baseline 还必须明确停止位置。对下标 i 来说，最多只能检查其余 n - 1 个位置：
- 如果其中出现更大值，取第一个。
- 如果全部检查完仍未找到，答案是
-1。 - 不能继续第二圈，也不能把起点自己作为候选。
这个 baseline 的 break 是：
我们已经知道人工观察顺序，但还没有一个可以执行的下标访问规则。普通的右侧区间会在数组末尾停止，无法自然回到开头。
现在这一版能做到：
- 准确说明循环数组中的右侧观察顺序。
- 区分“第一个严格更大值”和“环内最大值”。
- 明确一圈结束后必须停止，并为找不到答案的位置保留
-1。
它还缺：
- 一个可以运行的循环下标访问方法。
Step 2：先用模运算写出正确 baseline
当前 baseline 是：
从下标 i 出发，依次检查后面的 n - 1 个循环位置。
普通下标 i + step 可能越过数组末尾。现在需要增加一个真正执行绕回的规则：
next_index = (i + step) % n
当 i + step < n 时，结果仍是正常右侧下标；越过末尾后，取模会把它映射回数组开头。
先写一个正确版本：
from typing import List
def next_greater_elements_scan(nums: List[int]) -> List[int]:
n = len(nums)
answer = [-1] * n
for i in range(n):
for step in range(1, n):
next_index = (i + step) % n
if nums[next_index] > nums[i]:
answer[i] = nums[next_index]
break
return answer
内层循环从 1 开始，表示至少向右走一步；在 n 之前停止，因此恰好检查其余 n - 1 个位置，不会回到起点自己。
用 [1,2,1] 的最后一个下标 i = 2 检查：
step | (i + step) % n | 值 | 是否严格更大 |
|---|---|---|---|
| 1 | 0 | 1 | 否 |
| 2 | 1 | 2 | 是，写入答案并停止 |
运行检查：
assert next_greater_elements_scan([1, 2, 1]) == [2, -1, 2]
assert next_greater_elements_scan([5, 4, 3, 2, 1]) == [-1, 5, 5, 5, 5]
assert next_greater_elements_scan([1, 2, 3]) == [2, 3, -1]
assert next_greater_elements_scan([2, 2, 2]) == [-1, -1, -1]
assert next_greater_elements_scan([7]) == [-1]
现在这一版能做到：
- 正确访问每个下标后面的一整圈候选位置。
- 在遇到第一个严格更大值时立即停止。
- 对找不到答案的位置保留
-1。 - 正确处理全相等和单元素输入。
它还缺：
- 不同起点会反复检查相同的循环位置。
最坏情况下，每个下标都检查 O(n) 个候选位置，总时间复杂度是 O(n²)。除输出数组外，额外空间复杂度是 O(1)。
Step 3：把循环数组展开成虚拟的两遍
当前 baseline 为每个起点单独构造一圈访问顺序：
i + 1, i + 2, ..., i + n - 1
它的 break 是：
每个起点都在重复重建相同的环形顺序。我们需要先把“绕回开头”表示成一条统一的扫描路线。
对长度为 n 的数组，可以扫描虚拟位置：
i = 0, 1, 2, ..., 2n - 1
每个虚拟位置仍然通过下面的规则映射回原数组：
index = i % n
用 [1,2,1] 检查这条路线：
虚拟位置 i | 原始下标 i % n | 访问值 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 2 |
| 2 | 2 | 1 |
| 3 | 0 | 1 |
| 4 | 1 | 2 |
| 5 | 2 | 1 |
也就是：
原数组：1,2,1
第二遍：1,2,1
虚拟序列：1,2,1,1,2,1
为什么两遍足够？
- 第一遍负责正常的右侧后缀。
- 第二遍提供绕回后的数组前缀。
- 对任意原始下标，一遍后缀加一遍前缀已经覆盖其余所有候选位置。
- 第三遍只会再次看到相同候选，不会产生新答案。
此时只增加统一扫描路线：
for i in range(2 * n):
index = i % n
这段代码还不是完整算法，因为它只说明“当前访问哪个原始位置”，没有说明如何复用此前的比较结果。
现在这一版能做到：
- 把循环数组表示成长度为
2n的线性访问顺序。 - 让每个原始下标在两遍内看到完整的循环右侧候选。
- 解释为什么不需要无限循环或第三遍扫描。
它还缺：
- 一个能够记住哪些原始下标仍然没有答案的状态。
Step 4：只把还没有答案的原始索引压栈
当前 baseline 已经把循环顺序展开成两遍，但仍然只是不断访问元素。
它的 break 是：
当前较大值可能同时成为多个旧下标的答案。如果不保存这些仍在等待的下标，它们仍然需要各自重新扫描。
现在才加入一个栈 stack，保存还没有找到下一个更大元素的原始下标。
当虚拟位置映射到 index 后，当前值如果严格大于栈顶下标对应的值，就可以结算栈顶：
while stack and nums[index] > nums[stack[-1]]:
previous = stack.pop()
answer[previous] = nums[index]
这里必须保存下标，而不是只保存值：
- 需要知道答案应写入
answer的哪个位置。 - 需要保证每个原始位置只压栈一次。
两遍扫描只负责提供候选值，原始下标只在第一遍加入栈：
if i < n:
stack.append(index)
把这些变化接到上一版虚拟循环上：
answer = [-1] * n
stack = []
for i in range(2 * n):
index = i % n
while stack and nums[index] > nums[stack[-1]]:
previous = stack.pop()
answer[previous] = nums[index]
if i < n:
stack.append(index)
用 [1,2,1] 完整检查：
i | index | 当前值 | 操作 | 操作后的栈 | answer |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 第一遍，压入 0 | [0] | [-1,-1,-1] |
| 1 | 1 | 2 | 弹出 0，写入 2；压入 1 | [1] | [2,-1,-1] |
| 2 | 2 | 1 | 不能弹出 1；压入 2 | [1,2] | [2,-1,-1] |
| 3 | 0 | 1 | 与栈顶相等，不弹；第二遍不压栈 | [1,2] | [2,-1,-1] |
| 4 | 1 | 2 | 弹出 2，写入 2；第二遍不压栈 | [1] | [2,-1,2] |
| 5 | 2 | 1 | 不能弹出 1；第二遍不压栈 | [1] | [2,-1,2] |
栈中下标对应的值从栈底到栈顶保持非递增：
nums[stack[0]] >= nums[stack[1]] >= ...
相等值不会触发严格大于条件，因此可以同时留在栈中。最后仍在栈中的下标没有更大元素，answer 的初始值 -1 已经是正确结果。
现在这一版能做到：
- 用一个当前较大值连续结算多个未解决下标。
- 在第二遍中解决需要绕回数组开头的位置。
- 保证每个原始下标只在第一遍压栈一次。
- 对相等元素保持严格比较语义。
它还缺：
- 为什么弹栈时遇到的一定是第一个更大元素的完整 invariant。
- 为什么嵌套
while不会让复杂度退化为 O(n²)。 - LeetCode 方法封装和完整测试。
Step 5：为什么两遍扫描仍然是 O(n)
当前 baseline 已经能够运行栈机制，但还需要回答两个问题：
- 弹栈时的当前值为什么是那个下标的第一个更大元素？
- 外层扫描
2n次，内部还有while，为什么总时间仍然是 O(n)？
先固定循环 invariant：
处理每个虚拟位置前，
stack按压入顺序保存第一遍中仍未找到答案的原始下标；这些下标对应的值从栈底到栈顶非递增。
如果下标 previous 仍在栈中，说明此前已经扫描过的所有循环候选都没有严格大于 nums[previous]。当当前值第一次满足：
nums[index] > nums[previous]
它就是循环顺序中遇到的第一个更大元素，因此可以立即弹出并写入答案。
完整的 LeetCode 实现是：
from typing import List
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
answer = [-1] * n
stack = []
for i in range(2 * n):
index = i % n
while stack and nums[index] > nums[stack[-1]]:
previous = stack.pop()
answer[previous] = nums[index]
if i < n:
stack.append(index)
return answer
第一遍中，每个原始下标恰好压栈一次。第二遍不再压栈，只提供绕回后的候选值。
一个原始下标一旦弹出，就已经得到答案，不可能再次入栈或再次弹出。因此：
- 原始下标总压栈次数是
n。 - 总弹栈次数最多是
n。 - 外层循环执行
2n次。 - 所有
while迭代加起来最多n次。
所以总时间复杂度是 O(n)，而不是 O(n²)。
运行检查
solution = Solution()
assert solution.nextGreaterElements([1, 2, 1]) == [2, -1, 2]
assert solution.nextGreaterElements([5, 4, 3, 2, 1]) == [-1, 5, 5, 5, 5]
assert solution.nextGreaterElements([1, 2, 3]) == [2, 3, -1]
assert solution.nextGreaterElements([2, 2, 2]) == [-1, -1, -1]
assert solution.nextGreaterElements([7]) == [-1]
assert solution.nextGreaterElements([3, 1, 3]) == [-1, 3, -1]
复杂度
- 时间复杂度：O(n)。每个原始下标入栈一次、至多出栈一次。
- 额外空间复杂度：O(n)。答案数组和栈最多都保存 n 个位置。
常见错误
1. 第二遍继续压栈
如果两遍都执行 stack.append(index)，同一个原始下标会重复进入栈，破坏“一次入栈、一次出栈”的状态模型。
2. 使用 >= 弹栈
题目要求严格更大。相等元素不能成为答案，因此条件必须是：
nums[index] > nums[stack[-1]]
3. 只扫描一遍
只扫描原数组无法解决需要绕回开头的下标，例如 [1,2,1] 中最后一个 1。
4. 扫描超过两遍
两遍已经覆盖每个下标的一整圈未来候选。继续扫描不会产生新信息。
5. 看到嵌套 while 就判断为 O(n²)
复杂度应统计所有下标的总入栈和总出栈次数，而不是只看代码的语法嵌套。
小结
这道题的推导路线是：
固定循环数组中的第一个严格更大值
-> 用模运算为每个下标扫描一圈
-> 把循环顺序展开成虚拟两遍
-> 用栈保存第一遍中尚未得到答案的原始下标
-> 第二遍只提供候选值，不重复压栈
-> 每个原始下标最多入栈、出栈一次
503 对 739 的关键扩展不是换一个栈模板，而是增加循环数组的候选顺序，同时保持原始索引只压栈一次。
下一题可以做 LeetCode 84 Largest Rectangle in Histogram，继续训练“当前更小值触发弹栈结算”的边界模型。