下一个更大元素 II

环形 = 数组首尾相连成一个圈。走到末尾不停，绕回开头继续找，直到回到自己为止。

每个元素都可能向后扫将近 n 个，n 个元素就是 n×n 次比较，数据一大就慢得不行。

把「还没找到答案」的下标攒起来。一旦来了个大数，它可能正是这些等待者要找的答案，一次性结清。

下面动画里，紫色高亮的格子就是栈里「还在排队等更大数」的下标；蓝色是已结清、cur 指针是当前扫到的位置。盯住这三样怎么变。

走两圈就等于「每个数都向后看了一整圈」。第二圈不再往栈里压新下标，只用它们去结清第一圈还没解决的等待者。

准备 · 全部待解：答案先全填 -1（默认没人更大）。栈空着，准备装「还没找到更大元素的下标」。下方 RESULT 行就是实时答案，紫格会代表栈内容。

i=0 · 看 nums[0]=1：i=0，值是 1。栈是空的，没人在等它，直接把下标 0 压进栈（变紫）——它开始排队等自己的「更大元素」。

i=1 · 比一比栈顶：i 走到 1，值是 2。先和栈顶（紫格下标 0）比：栈顶值是 1，2 比 1 大！这意味着下标 0 苦等的更大数到了。

i=1 · 弹 0，结清答案：弹出下标 0，记下 答案[0]=2（RESULT 行第一格变 2）。它变成蓝色——已结清，离开栈。

i=1 · 压入下标 1：栈空了，轮到下标 1 自己排队——把它压栈（紫格移到下标 1），等它将来的更大数。

i=2 · 比一比栈顶：i 走到 2，值是 3。和栈顶（下标 1，值 2）比：3 比 2 大，又能结清一个。

i=2 · 弹 1，结清答案：弹出下标 1，记 答案[1]=3。下标 0、1 都已结清（蓝色）。栈又空了。

i=2 · 压入下标 2：把当前下标 2 压栈（紫格到下标 2），它开始排队。

i=3 · 比一比栈顶：i 走到 3，值是 4。和栈顶（下标 2，值 3）比：4 更大。每个新数进来，会把栈里所有比它小的等待者一口气结清。

i=3 · 弹 2，结清答案：弹出下标 2，记 答案[2]=4。前三个都结清了（蓝色）。

i=3 · 压入下标 3：把下标 3（值 4，全场最大）压栈排队。它能不能等到更大的？往下看。

i=4 · 比一比栈顶：i 走到 4，值是 3。和栈顶（下标 3，值 4）比：3 没有 4 大，结不了 4 的账，不弹。

i=4 · 压入下标 4：下标 4 自己也还没找到更大的，把它也压栈。现在紫格 = 下标 3 和 4，对应值 [4,3]，从底到顶递减。第一圈走完，这两个还没结清。

第二圈的作用：让末尾这些没找到答案的数，能去「看」开头的元素。第二圈只结账、不再压新下标，否则会重复处理。

i=5 (i%n=0) · 绕回看 nums[0]=1：i=5，i%n=0，cur 绕回开头看 nums[0]=1。栈顶下标 4 的值是 3，1 比 3 小，结不了账。第二圈不压栈，i 继续走。

i=6 (i%n=1) · 看 nums[1]=2：i=6，cur 移到下标 1，值 2。栈顶下标 4 的值还是 3，2 仍然不够大，不弹。继续。

i=7 (i%n=2) · 看 nums[2]=3：i=7，cur 移到下标 2，值 3。栈顶下标 4 的值也是 3，一样大不算「更大」，要严格大于才弹——这是个容易写错的细节，所以不动。

i=8 (i%n=3) · 看 nums[3]=4：i=8，cur 移到下标 3，值 4。和栈顶（下标 4，值 3）比：4 比 3 大！终于来了能结清下标 4 的数。

i=8 · 弹 4，结清答案：弹出下标 4，记 答案[4]=4——这正是「最后那个 3 绕一圈撞上下标 2 的 4」的过程！下标 4 变蓝结清，栈只剩下标 3。

i=9 (i%n=4) · 看 nums[4]=3：i=9，最后一步，cur 到下标 4，值 3。栈顶下标 3 的值是 4，3 比 4 小，结不了账。2n 步走完了。

收尾 · 栈里剩谁就是 -1：走完两圈，栈里还剩下标 3（值 4，全场最大）。它从没被弹出，说明绕一整圈都没人比它大，保持默认 -1。最终答案 [2,3,4,-1,4]。

关键账：每个下标最多入栈一次、出栈一次，2n 次循环里总操作数被钉死在常数倍 n，所以是 O(n)。

新来一个数，就把候车室里所有「比它小」的等待者一次结清。凡是「找下一个更大/更小」的题，第一反应就该想到单调栈。

每日温度(LC739)、下一个更大元素 I(LC496) 骨架完全一样，区别只在「存什么、比较方向、要不要绕圈」。

雷区实演 · 相等也弹会出错：nums=[3,3]，正确答案该是 [-1,-1]（没人严格更大）。但若比较写成 ≤，遇到第二个 3 会误判它「更大」，把答案[0] 错填成 3。所以必须严格 <。

边界三连：三种极端：只有一个数、严格递增、全部相同。能把这三种讲对，代码就稳了。

面试追问：把「O(n) 的均摊账」和「为什么走两圈」讲透，是这题的面试得分点。