本次刷题日记的第 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
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
