- 标签:栈、数组、哈希表、单调栈
- 难度:简单
描述:给定两个没有重复元素的数组 nums1
和 nums2
,其中 nums1
是 nums2
的子集。
要求:找出 nums1
中每个元素在 nums2
中的下一个比其大的值。
说明:
-
nums1
中数字x
的下一个更大元素是指:x
在nums2
中对应位置的右边的第一个比x
大的元素。如果不存在,对应位置输出-1
。 -
$1 \le nums1.length \le nums2.length \le 1000$ 。 -
$0 \le nums1[i], nums2[i] \le 10^4$ 。 -
$nums1$ 和$nums2$ 中所有整数互不相同。 -
$nums1$ 中的所有整数同样出现在$nums2$ 中。
示例:
- 示例 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 。
最直接的思路是根据题意直接暴力求解。遍历 nums1
中的每一个元素。对于 nums1
的每一个元素 nums1[i]
,再遍历一遍 nums2
,查找 nums2
中对应位置右边第一个比 nums1[i]
大的元素。这种解法的时间复杂度是
另一种思路是单调栈。
因为 nums1
是 nums2
的子集,所以我们可以先遍历一遍 nums2
,并构造单调递增栈,求出 nums2
中每个元素右侧下一个更大的元素。然后将其存储到哈希表中。然后再遍历一遍 nums1
,从哈希表中取出对应结果,存放到答案数组中。这种解法的时间复杂度是
-
使用数组
res
存放答案。使用stack
表示单调递增栈。使用哈希表num_map
用于存储nums2
中下一个比当前元素大的数值,映射关系为当前元素值:下一个比当前元素大的数值
。 -
遍历数组
nums2
,对于当前元素:- 如果当前元素值较小,则直接让当前元素值入栈。
- 如果当前元素值较大,则一直出栈,直到当前元素值小于栈顶元素。
- 出栈时,第一个大于栈顶元素值的元素,就是当前元素。则将其映射到
num_map
中。
- 出栈时,第一个大于栈顶元素值的元素,就是当前元素。则将其映射到
-
遍历完数组
nums2
,建立好所有元素下一个更大元素的映射关系之后,再遍历数组nums1
。 -
从
num_map
中取出对应的值,将其加入到答案数组中。 -
最终输出答案数组
res
。
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = []
stack = []
num_map = dict()
for num in nums2:
while stack and num > stack[-1]:
num_map[stack[-1]] = num
stack.pop()
stack.append(num)
for num in nums1:
res.append(num_map.get(num, -1))
return res
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。