LeetCode 496. Next Greater Element I 题解：Go 单调栈与哈希表实战

LeetCode 496. Next Greater Element I 题解：Go 单调栈与哈希表实战

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文以 LeetCode 496. Next Greater Element I 为切入点，讲解"下一个更大元素"（Next Greater Element, NGE）这一高频算法题型的定义、约束与两种经典解法：哈希表辅助的暴力扫描，以及单调栈（Monotonic Stack）优化。结合 LeetCode-Go 仓库中的 官方实现 与 单元测试，读者将掌握 NGE 问题的建模方法、Go 语言实现细节与复杂度权衡，并能顺势理解环形场景下的进阶变体（LeetCode 503）。

一、问题定义：什么是"下一个更大元素"

1.1 题目原文

题目给定两个数组nums1和nums2，其中nums1中的元素是nums2的子集，且两个数组内均不含重复元素。需要为nums1中的每一个元素x，在nums2中对应位置向右寻找第一个比x大的数，即 "Next Greater Number"；若不存在，则输出-1。

1.2 关键术语

• 下一个更大元素（NGE）：元素x在nums2中右侧（索引比x所在位置大）第一个大于x的数值，而非最大值、也非最右侧的值。
• 子集映射：nums1是nums2的子集，答案的查找位置以nums2为准，输出顺序与nums1保持一致。

1.3 示例一

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]. Output: [-1,3,-1] Explanation: For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1. For number 1 in the first array, the next greater number for it in the second array is 3. For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

逐步验证：

• 4在nums2中位于索引 2，其右侧只有2，2 < 4，故输出-1；
• 1在nums2中位于索引 0，向右第一个比1大的数是3（索引 1），输出3；
• 2在nums2中位于索引 3，右侧无元素，输出-1。

1.4 示例二

Input: nums1 = [2,4], nums2 = [1,2,3,4]. Output: [3,-1] Explanation: For number 2 in the first array, the next greater number for it in the second array is 3. For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

• 2位于nums2索引 1，右侧第一个大于2的是3；
• 4位于末尾，右侧无更大元素，输出-1。

1.5 约束条件（Note）

• nums1与nums2中的所有元素均唯一（无重复值，这一性质使哈希映射成为可能）；
• 两个数组的长度均不超过 1000（数据规模中等，暴力法在理论上是可行的，但单调栈更具推广价值）。

二、题目大意与题型定位

2.1 中文题意

题目给出 2 个数组 A 和 B，针对 A 中的每个元素，要求在 B 数组中找出比该元素大的数，且 B 中元素之间的顺序保持不变：即从该元素在 B 中的位置起向右扫描，找到第一个大于它的值就输出；找不到就输出-1。

2.2 题型归属

从仓库目录结构看，本题位于 leetcode/0496.Next-Greater-Element-I，与 0503.Next-Greater-Element-II（环形数组 + 单调栈）构成同一题型家族。"下一个更大元素"是单调栈最经典的入门场景，掌握它可以平滑迁移到柱状图最大矩形、每日温度、滑动窗口极值等大量栈类问题。

三、解法一：哈希表定位 + 线性扫描（仓库官方实现）

LeetCode-Go 仓库的 496 号实现 采用了"哈希表记录下标 + 向右扫描"的思路，完整代码如下：

package leetcode func nextGreaterElement(nums1 []int, nums2 []int) []int { if len(nums1) == 0 || len(nums2) == 0 { return []int{} } res, reocrd := []int{}, map[int]int{} for i, v := range nums2 { reocrd[v] = i } for i := 0; i < len(nums1); i++ { flag := false for j := reocrd[nums1[i]]; j < len(nums2); j++ { if nums2[j] > nums1[i] { res = append(res, nums2[j]) flag = true break } } if flag == false { res = append(res, -1) } } return res }

3.1 实现要点逐行拆解

1. 空值兜底：若nums1或nums2为空，直接返回空切片[]int{}，避免后续下标越界；
2. 建立值 → 下标的哈希表：遍历nums2，用map[int]int记录每个值在nums2中的索引（变量名reocrd为 "record" 的笔误，不影响逻辑）；
3. 遍历nums1查找 NGE：对每个元素，先从哈希表取出其在nums2中的起始下标，从该位置向右扫描：
   • 一旦发现nums2[j] > nums1[i]，即为"下一个更大元素"，记录后break；
   • 用flag标记是否找到；若扫描完仍未找到，追加-1。

3.2 复杂度分析

由于nums1、nums2长度均不超过 1000，最坏约 10⁶ 次比较，在 LeetCode 约束下完全可行，这也是该解法能被仓库收录为"简单题直接实现"的原因。

四、解法二：单调栈 + 哈希表（推荐推广版）

暴力法的缺点在于：对nums1的每个元素都重复向右扫描，信息未被复用。单调栈可以一次性为nums2中所有元素求出 NGE，再借助哈希表 O(1) 查询，将整体复杂度优化到 O(n + m)。

4.1 算法流程

1. 初始化：一个空栈stack（维护"尚未找到 NGE"的递减序列），一个哈希表nextGreater；
2. 从右向左遍历nums2（或从左向右，两种方向等价）：
   • 当栈非空且nums2[i] >= stack 顶时，不断出栈——栈顶这些更小（或相等）的元素不可能是nums2[i]的 NGE 候选；
   • 出栈结束后，若栈非空，则栈顶即nums2[i]的下一个更大元素，记入nextGreater；若栈空，则记为-1；
   • 将nums2[i]入栈；
3. 查询输出：遍历nums1，从nextGreater中取出每个元素的答案。

核心不变式：栈内元素自底向上严格递减，栈顶永远是最接近当前位置、且尚未匹配到 NGE 的元素。

4.2 Go 参考实现

func nextGreaterElement(nums1 []int, nums2 []int) []int { stack := []int{} nextGreater := make(map[int]int, len(nums2)) // 从右向左扫描 nums2，维护单调递减栈 for i := len(nums2) - 1; i >= 0; i-- { for len(stack) > 0 && stack[len(stack)-1] < nums2[i] { stack = stack[:len(stack)-1] // 弹出比当前值小的元素 } if len(stack) == 0 { nextGreater[nums2[i]] = -1 } else { nextGreater[nums2[i]] = stack[len(stack)-1] } stack = append(stack, nums2[i]) } res := make([]int, len(nums1)) for i, v := range nums1 { res[i] = nextGreater[v] } return res }

4.3 复杂度对比

单调栈将多次重复扫描合并为一次线性遍历，且不依赖"长度不超过 1000"的约束，可以平滑应对大规模数据，是面试与工程中的首选写法。

五、单调栈的可视化推演

以nums2 = [1, 3, 4, 2]、nums1 = [4, 1, 2]为例，从右向左执行单调栈：

最终nextGreater = {2: -1, 4: -1, 3: 4, 1: 3}，代入nums1得答案[-1, 3, -1]，与题目示例一完全一致。可以看出，栈顶元素就是"当前元素右侧最近且比它大"的候选，出栈动作天然保证了这一点。

六、单元测试验证：仓库测试用例剖析

仓库为本题配套了完整的 单元测试，采用"参数 + 期望答案"的结构化用例组织方式：

package leetcode import ( "fmt" "testing" ) type question496 struct { para496 ans496 } // para 是参数 // one 代表第一个参数 type para496 struct { one []int another []int } // ans 是答案 // one 代表第一个答案 type ans496 struct { one []int } func Test_Problem496(t *testing.T) { qs := []question496{ { para496{[]int{4, 1, 2}, []int{1, 3, 4, 2}}, ans496{[]int{-1, 3, -1}}, }, { para496{[]int{2, 4}, []int{1, 2, 3, 4}}, ans496{[]int{3, -1}}, }, { para496{[]int{}, []int{}}, ans496{[]int{}}, }, // 如需多个测试，可以复制上方元素。 } fmt.Printf("------------------------Leetcode Problem 496------------------------\n") for _, q := range qs { _, p := q.ans496, q.para496 fmt.Printf("【input】:%v 【output】:%v\n", p, nextGreaterElement(p.one, p.another)) } fmt.Printf("\n\n\n") }

6.1 测试设计要点

• 覆盖题目两个官方示例：验证[-1, 3, -1]与[3, -1]两组基准答案；
• 覆盖空输入边界：nums1、nums2均为空时返回[]int{}，与 实现源码 中的空值兜底分支一一对应；
• 结构化的 para/ans 组合：通过匿名结构体嵌套，把"输入参数"与"期望答案"绑定在一起，新增用例只需复制一条question496字面量，扩展成本极低。

这种para/ans测试模式在整个仓库中被大量复用，是 LeetCode-Go 一以贯之的工程化测试约定。运行方式遵循仓库标准流程：

go test -v ./leetcode/0496.Next-Greater-Element-I/...

（需在仓库根目录下执行，依赖 go.mod 中声明的 modulegithub.com/halfrost/LeetCode-Go。）

七、延伸进阶：环形变体 LeetCode 503

掌握了 496 的单调栈写法后，可以无缝迁移到同仓库的 503. Next-Greater-Element-II（环形数组，nums可视为首尾相接）。该题在 496 基础上仅多了一步：将数组"虚拟翻倍"，即遍历2 * len(nums)次，用i % len(nums)取模访问元素：

// 解法一 单调栈 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 }

注意这里栈中存的是下标而非数值，从而能直接回填结果数组res。i < len(nums)*2的取模遍历等价于在逻辑上把nums复制一份拼在尾部，保证了"环上每个元素都能在自身右侧（含绕环）找到 NGE"。该文件还同时给出了不使用单调栈的朴素解法nextGreaterElements1，两相对照，可以直观感受到单调栈对复杂度的收益。

八、总结

"下一个更大元素"是单调栈思维的第一块跳板：它把"为每个元素重复扫描"的冗余计算，压缩为"栈内元素严格单调、每个元素仅进出栈一次"的线性过程。建议读者对照 496 README 题解 亲手实现一遍暴力版与单调栈版，再用仓库测试用例校验，随后挑战 503 环形变体，即可完整掌握这一经典题型。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go