LeetCode 503. 下一个更大元素 II · Java 实现
题意
给定一个循环数组 nums，返回每个元素的"下一个更大元素"。若不存在则返回 -1。
与 496 题的区别：本题数组是环形的，可以绕回开头继续找。
示例：
nums = [1, 2, 1] 输出: [2, -1, 2]· 1 → 下一个更大的 2
· 2 → 后面没有更大的（绕一圈也没有），-1
· 1 → 绕回开头找到 2
思路一：单调栈 + 数组翻倍（推荐）
核心技巧：把数组"逻辑上"翻倍成 2n 长（nums[i % n]），这样环形问题就转化为线性问题。
· 维护一个单调递减栈（存下标，栈底到栈顶对应值递减）。
· 遍历 i ∈ [0, 2n - 1]，对当前值 nums[i % n]：
· 只要栈顶元素的值 小于 当前值，就说明找到了下一个更大元素，弹出并记录答案。
· 把当前下标压栈。
为什么遍历 2n - 1 就够了？
最后一位 i = 2n - 1 对应的下标是 n - 1，它的"下一个更大元素"只可能在 [n, 2n - 2] 中，正好覆盖了所有环回的可能，不需要再多走一圈。
importjava.util.ArrayDeque;importjava.util.Arrays;importjava.util.Deque;classSolution{publicint[]nextGreaterElements(int[]nums){intn=nums.length;int[]res=newint[n];Arrays.fill(res,-1);Deque<Integer>stack=newArrayDeque<>();// 存下标，栈内值单调递减for(inti=0;i<2*n-1;i++){intidx=i%n;while(!stack.isEmpty()&&nums[stack.peek()]<nums[idx]){res[stack.pop()]=nums[idx];}stack.push(idx);}returnres;}}注意：2n - 1 次遍历中，前 n 次是正常入栈，后 n - 1 次的作用只是查找、弹出，并不是真的再把下标压进去（其实压了也没关系，因为后面不会再被用到，只是栈会变长一点点）。如果你写 2 * n 也完全正确，只是多一次冗余判断。
思路二：暴力 O(n²)（仅作对照）
classSolution{publicint[]nextGreaterElements(int[]nums){intn=nums.length;int[]res=newint[n];for(inti=0;i<n;i++){res[i]=-1;for(intj=1;j<n;j++){intidx=(i+j)%n;if(nums[idx]>nums[i]){res[i]=nums[idx];break;}}}returnres;}}· 时间 O(n²)，会被大数据卡住，只适合理解题意。
思路三：Deque 存值 + 下标映射（不推荐）
有人会尝试 Map<value, value> 映射。因为数组有重复元素，value → next greater 映射会冲突，所以必须用下标入栈，这是本题的坑点之一。
复杂度
方法 时间 空间
单调栈（推荐） O(n) O(n)
暴力 O(n²) O(1)
每个下标最多入栈、出栈各一次，所以栈版本的总操作数是 O(n)。
关键坑点 ⚠️
- 必须用下标入栈，不能用值
· 数组里可能有重复元素（如 [2, 2, 3]），用 Map<Integer, Integer> 做映射会覆盖。
· 用下标才能唯一确定位置。 - 循环长度是 2 * n - 1，不是 2 * n
· 2n 也能对，但 2n - 1 更"紧"，是面试官爱问的细节。
· 原因：最后一个元素 (n-1) 的下一个更大元素只可能在 [n, 2n-2] 里出现，2n-1 这一位多余。 - 比较必须是 <，不能是 <=
· 相等不算"更大"，相等时不能弹出。
· 写成 <= 会导致 [2,2,3] 的前两个 2 错误地指向彼此。 - res 初始化为 -1，而不是 0
· 0 也未必是合法答案，正确默认值只能是 -1（题意：不存在则 -1）。 - ArrayDeque 不允许 push(null)
· 用 Deque 存下标（自动装箱），不会出问题；但别尝试 push(null)。 - 不要真的构造一个 2n 长的数组
· 用 i % n 取模即可，既省空间又符合"环形"语义。
一句话总结
环形问题 = 遍历两圈 + 取模，用单调栈在 2n - 1 次遍历中"出栈即找到答案"。栈存下标（防重复值），比较用严格 <，答案默认 -1。
