Leetcode 496.下一个更大元素Ⅰ

1.题目描述

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] 是如上所述的 下一个更大元素 。

输入：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 。

输入：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 中

2.思路分析

2.1 暴力解法

​ 本题需要寻找的是nums1中的每个元素值 nums1[i] 在 nums2中对应位置的右边的第一个比 nums1[i] 大的元素值。

步骤:

• 初始化与 nums1等长的查询数组 res。
• 遍历 nums1中的所有元素，不妨设当前遍历到元素为 nums1[i]：
  • 从前向后遍历 nums2 中的元素，直至找到 nums2[j]=nums1[i]；
  • 从 j+1 开始继续向后遍历，直至找到 nums2[k]>nums2[j]，其中 k≥j+1；
  • 如果找到了 nums2[k]， 则将 res[i] 置为[k]nums2[k]，否则将 res[i] 置为 -1
• 遍历结束后,数组res为最终结果。

2.2 单调栈

2.2.1 什么时候使用单调栈?

一般是一维数组,要寻找任一一个元素的右边或者左边第一个比自己大的或者小的元素的位置

2.2.2 单调栈的本质是什么?

以空间换时间

2.2.3 单调栈里存储的是什么?

存储元素的下标即可，如果需要获取对应的元素, 直接T[i]即可获取

2.2.4 单调栈里的元素是递增还是递减?

方向:栈顶->栈底

具体递增还是递减根据具体题目而定,本题还是递增(栈顶->栈底:小->大),这样才能找到右边第一个比自己大的元素。

本题是找nums1中的元素在nums2中下一个比当前元素大的元素，nums1是 nums2的子集。

在遍历nums2的过程中，我们要判断nums2[i]是否在nums1中出现过，因为最后是要根据nums1元

素的下标来更新result数组。 (nums1和nums2是两个没有重复元素的数组)

单调栈的三种判断情况: 本题使用递增

• 情况1:当前遍历元素T[i] < 栈顶元素 T[st.top()]的情况, T[i]入栈
• 情况2:当前遍历元素T[i] == 栈顶元素 T[st.top()]的情况, T[i]入栈
• 情况3:当前遍历元素T[i] > 栈顶元素 T[st.top()]的情况, 栈顶元素弹出, T[i]入栈, 记录结果

举个栗子,来说明以上三种情况:

nums1 = [4,1,2], nums2 = [1,3,4,2], 遍历nums2数组

• 遍历数组,加入T[0]
  

• 加入T[1]=3, 此时T[1]>T[0](情况3), 由于要保持单调栈的性质(此时使用递增顺序),故T[0]弹出,同时判断T[1]是否在在nums1中存在,存在保存到最后结果。
  

• 加入T[2]=4,此时T[2]>T1[1](情况3), 由于要保持单调栈的性质(此时使用递增顺序),故T[1]弹出,同时判断T[2]是否在在nums1中存在,存在保存到最后结果。
  

• 加入T[3]=2,此时T[3]

• 遍历结束后,返回result数组即可

3.代码实现

3.1 暴力解法

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        m, n = len(nums1), len(nums2)
        res = [0] * m
        for i in range(m):
            j = nums2.index(nums1[i])
            k = j + 1
            while k < n and nums2[k] < nums2[j]:
                k += 1
            res[i] = nums2[k] if k < n else -1
        return res
1
2
3
4
5
6
7
8
9
10
11

复杂度分析

• 时间复杂度：O(mn)，其中 m 是 nums1的长度，n 是 nums2的长度。
• 空间复杂度：O(1)

3.2 单调栈

# 写法1
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = [-1]*len(nums1)
        stack = [0]
        for i in range(1,len(nums2)):
            # 情况一情况二
            if nums2[i]<=nums2[stack[-1]]:
                stack.append(i)
            # 情况三
            else:
                while len(stack)!=0 and nums2[i]>nums2[stack[-1]]:
                    if nums2[stack[-1]] in nums1:
                        index = nums1.index(nums2[stack[-1]])
                        result[index]=nums2[i]
                    stack.pop()                 
                stack.append(i)
        return result
# 写法2
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # 单调栈
        result = [-1] * len(nums1)
        stack = []

        for i in range(len(nums2)):
            # 情况3:当前元素 > 栈顶元素 
            while stack and nums2[i] > nums2[stack[-1]]:
                # 记录结果的处理逻辑
                if nums2[stack[-1]] in nums1:
                    result[nums1.index(nums2[stack[-1]])] = nums2[i]
                stack.pop()
            # 情况1和情况2
            stack.append(i)
        return result
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

复杂度分析

• 时间复杂度：O(m + n)，其中 m 是 nums1的长度，n 是 nums2的长度。我们需要遍历 nums2以计算nums2中每个元素右边的第一个更大的值；需要遍历 nums1以生成查询结果。
• 空间复杂度：O(n)，用于存储哈希表。