下一个更大元素 II

怎样从“循环数组每个元素下一个更大。”推导出 单调栈 · 循环 NGE，并证明每次状态变化都不会漏掉答案？

中心结论：双倍长度或 modulo 索引,单调栈同样逻辑。

题目给出数组 A，针对 A 中的每个数组中的元素，要求在 A 数组中找出比该元素大的数，A 是一个循环数组。如果找到了就输出这个值，如果找不到就输出 -1。

在本站主例中，循环数组每个元素下一个更大。

算法最终需要得到或观察：循环 next greater 数组。

为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“单调候选队列”，明确答案需要观察什么。
2. 2状态只维护 栈、i mod n。
3. 3转移每一步按照 双倍长度或 modulo 索引,单调栈同样逻辑。
4. 4收尾读取 循环 next greater 数组。，并复核边界与复杂度。

栈或队列中保存的是仍未找到结论、且保持单调关系的下标。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：栈、i mod n。

这题是第 496 题的加强版，在第 496 题的基础上增加了循环数组的条件。这一题可以依旧按照第 496 题的做法继续模拟。更好的做法是用单调栈，栈中记录单调递增的下标。

双倍长度或 modulo 索引,单调栈同样逻辑。

执行过程中持续维护：栈、i mod n。

正确性依赖以下不变量：遍历 2n-1 或 n 次 mod 处理循环。

面试时可以压缩为：单调栈×2 O(n)。

落到当前题，执行机制可以压缩为：双倍长度或 modulo 索引,单调栈同样逻辑。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入循环数组每个元素下一个更大。 因为：双倍长度或 modulo 索引,单调栈同样逻辑。
2. 2单调递减栈找下一个更大准备逆序扫描。 因为：栈顶是右侧第一个更大。
3. 3nums[2]=1 的下一个更大 = -1维护递减栈并赋值。 因为：O(n) 单调栈。
4. 4nums[1]=2 的下一个更大 = -1维护递减栈并赋值。 因为：O(n) 单调栈。
5. 5nums[0]=1 的下一个更大 = 2维护递减栈并赋值。 因为：O(n) 单调栈。
6. 6NGE 数组完成全部处理完。 因为：经典单调栈模板。
7. 7单调递减栈找下一个更大准备逆序扫描。 因为：栈顶是右侧第一个更大。
8. 8收尾与复杂度循环 next greater 数组。 因为：时间 O(n) · 空间 O(1)。双倍长度或 modulo 索引,单调栈同样逻辑。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 单调栈
func nextGreaterElements(nums []int) []int {
	res := make([]int, 0)
	indexes := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		res = append(res, -1)
	}
	for i := 0; i < len(nums)*2; i++ {
		num := nums[i%len(nums)]
		for len(indexes) > 0 && nums[indexes[len(indexes)-1]] < num {
			index := indexes[len(indexes)-1]
			res[index] = num
			indexes = indexes[:len(indexes)-1]
		}
		indexes = append(indexes, i%len(nums))
	}
	return res
}

// 解法二
func nextGreaterElements1(nums []int) []int {
	if len(nums) == 0 {
		return []int{}
	}
	res := []int{}
	for i := 0; i < len(nums); i++ {
		j, find := (i+1)%len(nums), false
		for j != i {
			if nums[j] > nums[i] {
				find = true
				res = append(res, nums[j])
				break
			}
			j = (j + 1) % len(nums)
		}
		if !find {
			res = append(res, -1)
		}
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="next-greater", nums=[1,2,1]
    //    期望：循环 next greater 数组。
    //
    // 2. 失败 / 未命中
    //    检查：结果长度 n,别 push 两次答案。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC496；LC739
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意循环数组每个元素下一个更大。
2. 2重复为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。
3. 3优化双倍长度或 modulo 索引,单调栈同样逻辑。
4. 4证明遍历 2n-1 或 n 次 mod 处理循环。
5. 5复杂度时间 O(n)，空间 O(1)