下一个更大元素 I

怎样从“nums1=[4,1,2],nums2=[1,3,4,2] 对应 next greater。”推导出 单调栈 · 下一个更大 I，并证明每次状态变化都不会漏掉答案？

中心结论：对 nums2 单调栈,遇更大弹栈记录答案;map 值→nextGreater。

这道题也是简单题。题目给出 2 个数组 A 和 B，针对 A 中的每个数组中的元素，要求在 B 数组中找出比 A 数组中元素大的数，B 中元素之间的顺序保持不变。如果找到了就输出这个值，如果找不到就输出 -1。

在本站主例中，nums1=[4,1,2],nums2=[1,3,4,2] 对应 next greater。

算法最终需要得到或观察：nums1 对应 next greater。

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

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

1. 1建模把输入翻译成“单调候选队列”，明确答案需要观察什么。
2. 2状态只维护 栈、答案 map。
3. 3转移每一步按照 对 nums2 单调栈,遇更大弹栈记录答案;map 值→nextGreater。
4. 4收尾读取 nums1 对应 next greater。，并复核边界与复杂度。

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

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

对 nums2 单调栈,遇更大弹栈记录答案;map 值→nextGreater。

执行过程中持续维护：栈、答案 map。

正确性依赖以下不变量：栈维护递减,弹出时栈顶 next greater 是当前。

面试时可以压缩为：单调栈+哈希 O(n)。

落到当前题，执行机制可以压缩为：对 nums2 单调栈,遇更大弹栈记录答案;map 值→nextGreater。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums1=[4,1,2],nums2=[1,3,4,2] 对应 next greater。 因为：对 nums2 单调栈,遇更大弹栈记录答案;map 值→nextGreater。
2. 2单调递减栈找下一个更大准备逆序扫描。 因为：栈顶是右侧第一个更大。
3. 3nums[2]=2 的下一个更大 = 10维护递减栈并赋值。 因为：O(n) 单调栈。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5nums[1]=5 的下一个更大 = 10维护递减栈并赋值。 因为：O(n) 单调栈。
6. 6nums[0]=4 的下一个更大 = 5维护递减栈并赋值。 因为：O(n) 单调栈。
7. 7单调递减栈找下一个更大准备逆序扫描。 因为：栈顶是右侧第一个更大。
8. 8收尾与复杂度nums1 对应 next greater。 因为：时间 O(n) · 空间 O(1)。对 nums2 单调栈,遇更大弹栈记录答案;map 值→nextGreater。

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

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
}

func main() {
    // 1. 主例
    //    输入：mode="next-greater", nums=[4,5,2,10]
    //    期望：nums1 对应 next greater。
    //
    // 2. 失败 / 未命中
    //    检查：O(n) 预处理 nums2。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC503 循环；LC739 温度
}

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

1. 1题意nums1=[4,1,2],nums2=[1,3,4,2] 对应 next greater。
2. 2重复为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。
3. 3优化对 nums2 单调栈,遇更大弹栈记录答案;map 值→nextGreater。
4. 4证明栈维护递减,弹出时栈顶 next greater 是当前。
5. 5复杂度时间 O(n)，空间 O(1)