LeetCode:496_下一个更大元素I

思路

这类题有套路,需要用到单调栈。

image-20230425171030337

上图中绿色item想找到下一个比它大的值,只需要和红色item比较就行,而不需要和紫色的item比较。所以我们需要维护一个单调递增的栈,保存红色的值。

image-20230425170958670

通过依次比较,得出,5对应的答案是6。

下一个数字4,来寻求下一个比它大的值。

image-20230425171138692

同样的,2比5小,在这个数据结构中没有意义,他应该在5存入数据结构时抛出。也就是说,在寻找下一个比它大的值的时候,只需要和栈顶比较,如果栈顶大,那栈顶就是答案。否则抛出栈顶,继续比较。找到答案后,并入栈。

题目

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ,找出满足 nums1[i] == nums2[j] 的下标 j ,并且在 nums2 确定 nums2[j]下一个更大元素 。如果不存在下一个更大元素,那么本次查询的答案是 -1

返回一个长度为 nums1.length 的数组 ans 作为答案,满足 ans[i] 是如上所述的 下一个更大元素

 

示例 1:

输入:nums1 = [4,1,2], nums2 = [1,3,4,2].
输出:[-1,3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:
- 4 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。
- 1 ,用加粗斜体标识,nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。

示例 2:

输入:nums1 = [2,4], nums2 = [1,2,3,4].
输出:[3,-1]
解释:nums1 中每个值的下一个更大元素如下所述:
- 2 ,用加粗斜体标识,nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ,用加粗斜体标识,nums2 = [1,2,3,4]。不存在下一个更大元素,所以答案是 -1 。

 

提示:

  • 1 <= nums1.length <= nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 104
  • nums1nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2

 

进阶:你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗?

Related Topics
  • 数组
  • 哈希表
  • 单调栈
  • 👍 1004
  • 👎 0
  • 代码

    func nextGreaterElement(nums1 []int, nums2 []int) []int {
        resMap := make(map[int]int, len(nums2))
        stack := make([]int, 0, len(nums2))
        for i := len(nums2) - 1; i >= 0; i-- {
            for len(stack) > 0 && nums2[i] >= stack[len(stack)-1] {
                stack = stack[:len(stack)-1]
            }
            if len(stack) > 0 {
                resMap[nums2[i]] = stack[len(stack)-1]
            } else {
                resMap[nums2[i]] = -1
            }
            stack = append(stack, nums2[i])
        }
    
        resArr := make([]int, 0, len(nums1))
        for i := 0; i < len(nums1); i++ {
            resArr = append(resArr, resMap[nums1[i]])
        }
        return resArr
    }
    作者:Yuyy
    博客:https://yuyy.info
    暂无评论

    发送评论 编辑评论

    
    				
    |´・ω・)ノ
    ヾ(≧∇≦*)ゝ
    (☆ω☆)
    (╯‵□′)╯︵┴─┴
     ̄﹃ ̄
    (/ω\)
    ∠( ᐛ 」∠)_
    (๑•̀ㅁ•́ฅ)
    →_→
    ୧(๑•̀⌄•́๑)૭
    ٩(ˊᗜˋ*)و
    (ノ°ο°)ノ
    (´இ皿இ`)
    ⌇●﹏●⌇
    (ฅ´ω`ฅ)
    (╯°A°)╯︵○○○
    φ( ̄∇ ̄o)
    ヾ(´・ ・`。)ノ"
    ( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
    (ó﹏ò。)
    Σ(っ °Д °;)っ
    ( ,,´・ω・)ノ"(´っω・`。)
    ╮(╯▽╰)╭
    o(*////▽////*)q
    >﹏<
    ( ๑´•ω•) "(ㆆᴗㆆ)
    😂
    😀
    😅
    😊
    🙂
    🙃
    😌
    😍
    😘
    😜
    😝
    😏
    😒
    🙄
    😳
    😡
    😔
    😫
    😱
    😭
    💩
    👻
    🙌
    🖕
    👍
    👫
    👬
    👭
    🌚
    🌝
    🙈
    💊
    😶
    🙏
    🍦
    🍉
    😣
    Source: github.com/k4yt3x/flowerhd
    颜文字
    Emoji
    小恐龙
    花!
    上一篇
    下一篇