LeetCode 496+503. 下一个更大元素系列——单调栈循环数组处理
LeetCode 496+503. 下一个更大元素系列——单调栈循环数组处理
适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约22分钟 | 难度：中等
开篇故事
上一篇讲了每日温度，有同学私信我说：「老张，我懂了单调栈基础，但我刷到 503 那道循环数组，脑子就宕机了，怎么处理环形的情况？」
这个问题问得好，循环数组是单调栈里第一个真正的难点。普通数组，我们从左往右扫一遍就完事了。循环数组呢？末尾的元素可以「绕回来」找前面的更大元素，这就打破了线性扫描的假设。
解决方案有一个非常经典的技巧：把数组复制一遍，拼接在后面，长度变为 2n，然后用下标取模来访问原数组。这个思路简单、暴力，但却是面试中考察最多的标准答案。
今天我们把 496 和 503 放在一起讲，看看从「两个不同数组间的查找」到「循环数组的查找」，单调栈的思路是怎么演进的。
一、题目解析
LeetCode 496. 下一个更大元素 I
题目： 给你两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对于每个 nums1[i]，在 nums2 中找出 nums1[i] 右边第一个比它大的元素。
示例：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2]
输出：[-1,3,-1]
解释：nums1[0]=4，在nums2中4的右边是2，没有比4大的，所以-1
nums1[1]=1，在nums2中1的右边是3，比1大，所以3
nums1[2]=2，在nums2中2的右边没有元素，所以-1核心约束：
nums1是nums2的子集- 所有元素不重复
LeetCode 503. 下一个更大元素 II
题目： 给一个循环数组 nums，对于每个元素，找出下一个更大的元素（可以绕过数组末尾继续查找）。
示例：
输入：nums = [1,2,1]
输出：[2,-1,2]
解释：nums[0]=1，下一个更大是2（nums[1]）
nums[1]=2，在循环中没有更大的，所以-1
nums[2]=1，绕回来，下一个更大是2（nums[1]）二、解法一（496）：暴力查找
思路分析
最直接的思路：对于 nums1 中的每个元素，先找到它在 nums2 中的位置，然后从那个位置向右扫描寻找更大元素。
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] result = new int[m];
for (int i = 0; i < m; i++) {
// 在 nums2 中找到 nums1[i] 的位置
int pos = -1;
for (int j = 0; j < n; j++) {
if (nums2[j] == nums1[i]) {
pos = j;
break;
}
}
// 从 pos+1 向右找第一个更大的
result[i] = -1; // 默认找不到
for (int j = pos + 1; j < n; j++) {
if (nums2[j] > nums1[i]) {
result[i] = nums2[j];
break;
}
}
}
return result;
}
}复杂度分析
- 时间复杂度：O(m × n)。对 nums1 的每个元素，在 nums2 中做两次线性扫描。
- 空间复杂度：O(1)。
三、解法二（496）：单调栈 + HashMap 预处理
思路分析
更聪明的做法：先对 nums2 整体用单调栈处理，建立每个元素到其「下一个更大元素」的映射，存入 HashMap。然后对 nums1 的每个元素，直接查表得到答案。
import java.util.*;
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// 第一步：对 nums2 建立「元素 -> 下一个更大元素」的映射
Map<Integer, Integer> map = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>(); // 存值（因为nums2无重复）
for (int num : nums2) {
// 当前元素比栈顶大，找到了栈顶的下一个更大元素
while (!stack.isEmpty() && num > stack.peek()) {
map.put(stack.pop(), num);
}
stack.push(num);
}
// 栈中剩余的元素，右边没有更大的，不存入map（查询时返回-1）
// 第二步：查询 nums1 中每个元素
int[] result = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
result[i] = map.getOrDefault(nums1[i], -1);
}
return result;
}
}复杂度分析
- 时间复杂度：O(m + n)。预处理 nums2 是 O(n)，查询 nums1 中 m 个元素是 O(m)。
- 空间复杂度：O(n)。HashMap 和单调栈最多存 n 个元素。
这才是 496 的最优解。注意：这里栈里存的是值而不是下标，因为 nums2 元素不重复，用值作为 HashMap 的 key 更方便。
四、解法三（503）：循环数组 + 单调栈（最优）
核心技巧：数组复制/取模模拟循环
处理循环数组的标准技巧：把数组在逻辑上复制一倍，遍历 2n 次，用 i % n 来访问实际元素。
为什么这样有效？循环数组中，任何元素最多向右看一圈，超过 n 步就回到了自己。所以遍历 2n 次就足够覆盖所有「跨越末尾」的情况。
完整代码
import java.util.*;
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1); // 默认找不到，赋值-1
// 单调递减栈，存下标
Deque<Integer> stack = new ArrayDeque<>();
// 遍历两倍长度，模拟循环数组
for (int i = 0; i < 2 * n; i++) {
int cur = nums[i % n]; // 用取模访问实际元素
// 当前元素比栈顶大，找到了答案
while (!stack.isEmpty() && cur > nums[stack.peek()]) {
int idx = stack.pop();
result[idx] = cur;
}
// 只在第一轮（i < n）时才把下标压栈
// 第二轮的元素只用来帮助弹出第一轮的元素，自身不需要查找答案
if (i < n) {
stack.push(i);
}
}
return result;
}
}手动模拟
以 nums = [1,2,1] 为例，n=3，遍历 2*3=6 次：
| i | i%n | cur | 栈（下标） | 操作 | result更新 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | [] | 压入0 | - |
| 1 | 1 | 2 | [0] | 2>1弹0，压入1 | result[0]=2 |
| 2 | 2 | 1 | [1] | 1<2，压入2 | - |
| 3 | 0 | 1 | [1,2] | 1<1(nums[2])，不弹，i>=n不压栈 | - |
| 4 | 1 | 2 | [1,2] | 2>1弹栈顶2，i>=n不压栈 | result[2]=2 |
| 4 | 1 | 2 | [1] | 2>2? 不，停止 | - |
| 5 | 2 | 1 | [1] | 1<2，不弹，i>=n不压栈 | - |
栈中剩余[1]，result[1]保持-1。
最终：result = [2, -1, 2]，正确！
复杂度分析
- 时间复杂度：O(n)。每个元素最多入栈一次出栈一次，总操作 2n 次（第二轮只出不入）。
- 空间复杂度：O(n)。栈的大小。
五、举一反三
496 的变体：有重复元素时
题目说 nums2 没有重复元素，所以可以用值做 HashMap 的 key。如果有重复元素，就必须存下标：
// 有重复元素的版本
Map<Integer, Deque<Integer>> indexMap = new HashMap<>();
for (int i = 0; i < nums2.length; i++) {
indexMap.computeIfAbsent(nums2[i], k -> new ArrayDeque<>()).push(i);
}503 循环数组扩展
循环数组的单调栈模板：
public int[] solveCircularArray(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) {
while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
result[stack.pop()] = nums[i % n];
}
if (i < n) stack.push(i); // 关键：只在第一轮压栈
}
return result;
}记住这个关键点： if (i < n) stack.push(i)，第二轮只用于触发弹出，不往栈里加新元素。
六、踩坑实录
坑一：503 中第二轮也压栈，导致结果出错
这是 503 最常见的错误。如果第二轮也压栈，栈里会有重复的下标（0到n-1各出现两次），最终 result[idx] 会被覆盖或者出现错误。
错误写法：
for (int i = 0; i < 2 * n; i++) {
while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
result[stack.pop()] = nums[i % n];
}
stack.push(i % n); // 错误！第二轮也压了
}正确写法：
if (i < n) {
stack.push(i); // 只在第一轮压栈
}坑二：Arrays.fill 忘记预填 -1
503 的答案默认值是 -1（找不到更大元素），而 Java 数组默认初始化是 0。如果忘记 Arrays.fill(result, -1) 就会出现 0 混在答案里的情况，而且测试用例中有 0，不容易发现。
// 必须先填充
int[] result = new int[n];
Arrays.fill(result, -1); // 不能忘！坑三：496 中对 nums2 建栈时用值还是下标
如前所述，496 的 nums2 无重复，可以用值；如果有重复就必须用下标。考试中容易套模板，无脑用下标，然后发现 HashMap 的 key 应该是值，弄混了。
建议记住：
- 无重复元素且只需知道元素值 → 栈存值
- 有重复元素或需要知道位置 → 栈存下标
坑四：遍历 2n 次但 i % n 取模时没意识到边界
遍历到 i = 2n-1 时，i % n = n-1，这是最后一个元素，没有问题。但有些同学在下标计算时会写成 (i+1) % n 或者 i % (n-1)，直接造成数组越界或逻辑错误。
一定要确认： 遍历下标是 i，访问元素用 nums[i % n]，仅此而已。
七、总结
今天把「下一个更大元素」系列的两道题系统讲完了。
496 的核心： 先对 nums2 用单调栈预处理，建立值到下一更大值的映射，再用 HashMap O(1) 查询 nums1 中的每个元素。整体时间 O(m+n)，比暴力 O(m×n) 快得多。
503 的核心： 循环数组用「遍历 2n 次 + 取模访问 + 只在第一轮压栈」的经典技巧，把循环问题转化为线性问题。
这两道题放在一起，展示了单调栈在不同场景下的灵活应用。循环数组这个技巧在很多题目里都会用到，务必记住。