「亚麻」刷 496 ~ 下一个较大的数
基本信息
- 题号:496
- 题厂:亚麻
- 难度系数:低
有 2 个数列:nums1 = [4,1,2], nums2 = [1,3,4,2],给 nums1 的元素找出下一个比自己大的元素,并按顺序返回……如果找不到这样的数,就返回 -1 返回 [-1,3,-1] 4 : 在nums2 中没有比自己大的,所以无解,返回 -1 1:在 nums2 中比自己大且排在它后面的是 3 2:在 nums2 最尾,没有下一个元素了……返回 -1
解题思路
- 不知道什么是 「monotonic stack」的小白,是不可能做出这道题的。
- 「monotonic stack」也是一种 stack。除了普通 stack 后进先出原理,monotonic stack 在放入元素时,只往里面塞比最后一个元素小的元素,所以 monotonic stack 里的元素不是递增就是递减……
- 我们往 「monotonic stack」有序塞元素,一般除了要知道元素的 value 值,还需要知道一点别的信息,比如 index 之类的——不然后续怎么操作……所以,monotonic stack 的元素一般是成双成对,甚至✖️ 3 ……
class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: # 初始化一个和 nums1 等长的数组,用于返回 # 填入 -1,默认都没找到 res = [-1] * len(nums1) # 创建 monotonic stack # 配对元素 [nums1 val, nums1 index] stack = [] # for 循环遍历 nums2 # 当 stack 最后一个元素的 value 值比当前 n 小时,说明 n 是要找的下一个比较大的数; # 于是我们把最后一个配对元素从 stack 中 pop 出,在根据提前记录好的 index 到 res 标记…… for n in nums2: while stack and stack[-1][0] < n: [val, index] = stack.pop() res[index] = n # 如果 n 在 nums1 里,我们需要把 n 在 nums1 的对应 index 值找到,然后配对存入 stack 用于后续查找…… if n in nums1: idx = nums1.index(n) stack.append([n, idx]) return res
Constraints
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
All integers in nums1 and nums2 are unique.
All the integers of nums1 also appear in nums2.
做题前要向考官讨论,nums1 和 nums2 的值的唯一性等等……
测试
- nums1 长度为 1 的边界情况
- nums2 一直降序或一直升序的情况,还有随机摆位的正常情况……
- ……
Big O
时间复杂度:O(n)
- 空间复杂度:O(n)
总结
- 「monotonic stack」还是比较玄乎的😭