下一个更大元素 I：单调递减栈一次扫清
答案在弹出时写下。当前数比栈顶大，栈顶右边第一个更大的就是它。
在 nums2 上维护从底到顶递减的栈。扫到 x 时，所有小于 x 的栈顶都被 x 打败：弹出并记 next[栈顶]=x，再把 x 压进去。扫完还留在栈里的数右边没有更大，记 −1。nums1 是 nums2 的子集，按 nums1 的顺序查这张表即可。每个数入栈出栈各一次，时间 O(n+m)。
这是 LeetCode 496. Next Greater Element I。nums1 是 nums2 的子集，两数组里的数都互不相同。对 nums1 里的每个数 x，在 nums2 里找到 x，再看它右边第一个比它大的数；没有就记 −1。按 nums1 的顺序返回这些答案。
主例 nums1 = [4, 1, 2]，nums2 = [1, 3, 4, 2]。4 在 nums2 里右边只有 2，没有更大，−1；1 右边第一个更大是 3；2 已经在最右，−1。答案 [-1, 3, -1]。
对 nums1 的每个查询从 x 的位置往右扫，最坏 O(n·m)。缺的不是「右边有没有更大」，而是 nums2 被同一段右侧反复扫描。本文在 nums2 上走一遍单调栈，弹出时把答案写进哈希，最后只查表。
查询可以等，nums2 不能扫两遍
朴素做法对 nums1 的每个 x 先在 nums2 里定位，再向右找第一个更大。主例三次查询分别走过 [2]、[3,4,2]、[]，短，看起来不疼。nums2 一长，同一段右侧会被每个较小的左边元素各扫一次。
观察：一个数的「下一个更大」只取决于它右边，和 nums1 无关。nums1 只决定输出顺序。所以应先在 nums2 上把每个值的答案算完，再按 nums1 取。
还缺一个结构：左边那些「还没被更大的数打败」的人，应该按从近到远排好，让新来的 x 一次性能把所有比自己小的人结算掉。后进的更靠右、更近，先被 x 检查——这又是栈。栈里保持递减，是为了保证栈顶就是「离 x 最近、还在等更大」的那一个。
被弹出的栈顶，答案就是当前数
从左到右扫 nums2，栈里存放还没有下一个更大元素的值，自底到顶递减。遇到 x：当栈不空且栈顶 < x，栈顶的右边第一个更大就是 x，写入哈希并弹出；直到栈空或栈顶 ≥ x，再把 x 压入。x 自己也开始等待。
为什么不会漏、不会错？被弹出的栈顶和 x 之间，没有比栈顶更大的数——否则它早就被中间那个数弹出了。所以 x 确实是它右边第一个更大。比 x 大的旧栈顶继续留着，等更右边。
用手走主例 nums2 = [1, 3, 4, 2]。1 入栈，栈 [1]。3 > 1，弹出 1，记下 1→3，3 入栈，栈 [3]。4 > 3，弹出 3，记下 3→4，4 入栈，栈 [4]。2 < 4，2 入栈，栈 [4, 2]。扫完，4 和 2 右边都没有更大，记 4→−1、2→−1。演示四帧就是这四步；最后一帧按 nums1 = [4, 1, 2] 查表，得到 [-1, 3, -1]。
每个值最多入栈一次、出栈一次，扫 nums2 是 O(n)，填 nums1 是 O(m)。题目保证数不重复，才能用「值 → 下一个更大」当哈希键；若有重复，栈里必须存下标。
答案写在弹出时入栈只是报到。真正找到「右边第一个更大」的时刻是被更大的新元素弹出去。扫完还留在栈里的人，右边已经没有人了，只能写 −1。
Go：单调递减栈
func nextGreaterElement(nums1, nums2 []int) []int {next := map[int]int{}stack := []int{}for _, x := range nums2 {for len(stack) > 0 && stack[len(stack)-1] < x {next[stack[len(stack)-1]] = xstack = stack[:len(stack)-1]}stack = append(stack, x)}for _, v := range stack { next[v] = -1 }res := make([]int, len(nums1))for i, v := range nums1 { res[i] = next[v] }return res}
1next 按值记账。本题数不重复，值可以当键。
2内层循环才是结算：栈顶 < x，栈顶的下一个更大就是 x。主例 3 弹出 1，4 弹出 3。
3x 自己入栈继续等。2 打不过 4，只能压在 4 上面。
4循环结束后栈里剩下的人右边已经走完，一律 −1。
5nums1 只决定输出顺序，不再回头扫 nums2。
总结
递减栈里等更大。主例 3 结算 1，4 结算 3，2 和 4 写 −1，查 nums1 得 [-1,3,-1]。
- nums1 是查询表，不是扫描对象。下一个更大只在 nums2 上算一次。
- 答案写在弹出时。还留在栈里的数，右边没有更大。
- 每个元素入栈出栈各一次。环形版本是 LC503，温度版是 LC739。