【刷题日记】496. 下一个更大元素 I

本次刷题日记的第 99 篇，力扣题为：496. 下一个更大元素 I

一、题目描述：

咱接下里三连刷 下一个更大元素 I，II，III，本次先来刷 496. 下一个更大元素 I

二、这道题考察了什么思想？你的思路是什么？

对于这道题，还是要仔细和细心去看题目的要求的，不然就很容易出幺蛾子，审题相当关键

• 题目中给出两个整数数组，nums1，nums2，且 nums1 是 nums2 的自己，数组里面的元素没有重复的情况，题目要求我们找到 nums1 中的每一个数字在 nums2 中的下一个更大元素，如果能找到，则记录实际的值，如果找不到，则记录 -1，最后返回一个结果数组即可
• 此处需要重点关注的是，下一个更大元素的含义是指 第一个比 x 大的数字，而不是指当前位置的下一个元素是否比自己大

分析

来审视一下这道题，如果一开始我们存在曲解题目的含义，那么我们可以能就会想歪，例如题目要求我们是要找到下一个更大的值（第一个比 x 大的数字），我们理解成找下一个更大的值（x 下一个数字是否比 x 大）

那么，其实我们不难写出这样的代码：

• 遍历 nums2 ，用哈希表记录 nums2 值与索引的关系，key 是 nums2 的值，value 是 nums2 的索引
• 遍历 nums1，用 nums1 的元素通过 hash 表找到 nums2 值对应的索引，然后找到当前 nums2 索引的下一个索引对应的值，进行和当前值比较即可，若当前值大，则记录 -1，反之记录实际的值

可是，这个代码是没有办法成功通过所有用例的，如下

因此，咱们审题的时候一定要仔细和重视题目给出的信息

那么接下来咱们思考如何找到下一个更大的值（第一个比 x 大的数字）时，我们可以复用上面做法的 hash 表，还是用于最后存储结果的

那么问题就来了，如果高效的找到 nums2 中每一个元素的下一个更大的值呢，并将结果存储到 hash 表中

不难想出直接暴力求解，2 个 for 循环嵌套，完成查找，结果写到 hash 表，最终转换成结果需要的数组即可

但是，咱们还应该思考更加好的方式，毕竟暴力求解时间复杂度太高，不符合题目说的进阶要求

那么这个时候，我们能不能做到只能遍历一次 nums1，遍历一次 nums2 来完成呢，而不是他们俩嵌套的实现

既然这样，求解数字右侧更大的一个数字，那么咱们就从右往左进行遍历 nums2，找到每一个元素的右边更大的一个元素，加入一个栈空间来帮助我们完成这个想法

思路是这样的：

• 从右向左遍历 nums2
• 判断当前元素是否大于栈顶元素，如果大于，那么很明显，当前元素的下一个更大元素绝对不可能是栈顶里面的值，因此需要剔除栈顶元素
• 直到当前元素小于栈顶元素，说明当前元素的下一个更大的元素就是栈顶元素的值，则记录当前元素的下一个更大元素到 hash 表中
• 如果发现剔除栈顶元素后，栈空了，说明当前元素的下一个更大的元素，不存在，则记录为 -1 到 hash 表中
• 处理上一步之后，将当前元素加入到入栈

例如，题目中给出的示例，我们可以这样来推演：

nums1 = [4,1,2], nums2 = [1,3,4,2]

这个时候，我们直接去遍历 nums1，然后去 hash 表中找对应结果即可

至此，相信 xdm 也能明白本题的做法以及思路了吧，剩下的，咱们就来手撸代码，完成最后一步吧

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

• 先倒序遍历 nums2，完成 hash 表的输出
• 正序遍历 nums1，找到 hash 表中的对应关系即可

编码如下：

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    help := map[int]int{}
    stack := []int{}
    res := []int{}
    for i:=len(nums2)-1; i>=0; i--{
        // 若当前元素大于栈顶，则栈顶元素出栈
        tmpNum := nums2[i]
        for len(stack) > 0 && tmpNum > stack[len(stack) -1] {
            stack = stack[:len(stack)-1]
        }
        if len(stack) == 0 {
            help[tmpNum] = -1
        }else{
            help[tmpNum] = stack[len(stack) -1]
        }
        stack = append(stack, tmpNum)
    }
    for _,num := range nums1 {
        res = append(res, help[num])
    }
    return res
}

四、总结：

本题的咱们这种处理方式属于哈希表 + 单调栈的方式，时间复杂度是 O(m+n) ，其中 m 是 nums1 的长度，n 是 nums2 的长度，咱们遍历 nums2 处理单调栈，遍历 nums1 来从 hash 表生成数据

空间复杂度是 O(n) ，因此咱们 hash 占用的空间是以 nums2 为基准来开辟的元素

原题地址：496. 下一个更大元素 I

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~