「亚麻」刷 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」还是比较玄乎的😭