「亚麻」刷 496 ~ 下一个较大的数

土豆炒青椒
·
·
IPFS
chatgpt 被禁了,说明刷题还得靠人脑……

基本信息

  • 题号: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」还是比较玄乎的😭


CC BY-NC-ND 2.0 授权

喜欢我的作品吗?别忘了给予支持与赞赏,让我知道在创作的路上有你陪伴,一起延续这份热忱!