​

496. 下一个更大元素 I

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：

1
2
3
4
5
6
>输入：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：

1
2
3
4
5
>输入：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
  • nums1和nums2中所有整数 互不相同
  • nums1 中的所有整数同样出现在 nums2 中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    dic := make(map[int]int)
    ans := make([]int, len(nums1))
    for k, v := range nums1 {
        dic[v] = k
    }
    var st []int
    n := len(nums2)
    for k:=range ans{
        ans[k]=-1
    }
    for i := n - 1; i >= 0; i-- {
        // 当前的值大于栈内的元素的值  栈内的小于这个的值是无用的值 
        // 出栈 
        for len(st) != 0 && nums2[i] >= st[len(st)-1] {
            st = st[:len(st)-1]
        }
        // 栈内元素不是空的 站顶的元素是大于当前元素的 也就是答案
        if len(st) != 0 {
            // 因为数组二可能包含没有数组1的值  使用字典记录
            if val, ok := dic[nums2[i]]; ok {
                // 返回栈顶元素 也就是第一个大于当前元素的值
                ans[val] = st[len(st)-1]
            }
        }
        // 追加当前元素到栈内
        st = append(st, nums2[i])
    }
    return ans
}
// 从前往后
func nextGreaterElement(nums1 []int, nums2 []int) []int {
    dic := make(map[int]int)
    ans := make([]int, len(nums1))

    for k, v := range nums1 {
        dic[v] = k
    }
    var st []int
    for k := range ans {
        ans[k] = -1
    }
    for _, v := range nums2 {
        // 栈顶元素大于当前元素 说明这个元素可能存在
        for len(st) != 0 && v > st[len(st)-1] {
            if val, ok := dic[st[len(st)-1]]; ok {
                ans[val] = v
            }
            st = st[:len(st)-1]
        }
        st = append(st, v)
    }
    return ans
}

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章