496. 下一个更大元素 I
496. 下一个更大元素 I
🟢 🔖 栈
数组
哈希表
单调栈
🔗 力扣
LeetCode
题目
The next greater element of some element x
in an array is the first greater element that is to the right of x
in the same array.
You are given two distinct 0-indexed integer arrays nums1
and nums2
, where nums1
is a subset of nums2
.
For each 0 <= i < nums1.length
, find the index j
such that nums1[i] == nums2[j]
and determine the next greater element of nums2[j]
in nums2
. If there is no next greater element, then the answer for this query is -1
.
Return an arrayans
of lengthnums1.length
such thatans[i]
is the next greater element as described above.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3, 4 ,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [ 1 ,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4, 2 ]. There is no next greater element, so the answer is -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1, 2 ,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3, 4 ]. There is no next greater element, so the answer is -1.
Constraints:
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10^4
- All integers in
nums1
andnums2
are unique. - All the integers of
nums1
also appear innums2
.
Follow up: Could you find an O(nums1.length + nums2.length)
solution?
题目大意
题目给出 2 个数组 A 和 B,针对 A 中的每个数组中的元素,要求在 B 数组中找出比 A 数组中元素大的数,B 中元素之间的顺序保持不变。如果找到了就输出这个值,如果找不到就输出 -1
。
解题思路
- 使用单调递增栈;
- 因为
nums1
是nums2
的子集,所以我们可以先遍历一遍nums2
,并构造单调递增栈; - 求出
nums2
中每个元素右侧下一个更大的元素,然后将其存储到哈希表中; - 再遍历一遍
nums1
,从哈希表中取出对应结果,存放到答案数组中; - 这种解法的时间复杂度是
O(n)
。
代码
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var nextGreaterElement = function (nums1, nums2) {
let map = new Map();
let stack = [];
for (let num of nums2) {
while (stack.length && stack[stack.length - 1] < num) {
map.set(stack.pop(), num);
}
stack.push(num);
}
for (let i = 0; i < nums1.length; i++) {
nums1[i] = map.has(nums1[i]) ? map.get(nums1[i]) : -1;
}
return nums1;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
503 | 下一个更大元素 II | [✓] | 栈 数组 单调栈 | |
556 | 下一个更大元素 III | 数学 双指针 字符串 | ||
739 | 每日温度 | [✓] | 栈 数组 单调栈 | |
2104 | 子数组范围和 | 栈 数组 单调栈 | ||
2281 | 巫师的总力量和 | 栈 数组 前缀和 1+ | ||
2454 | 下一个更大元素 IV | 栈 数组 二分查找 3+ | ||
2487 | 从链表中移除节点 | 栈 递归 链表 1+ | ||
2996 | 大于等于顺序前缀和的最小缺失整数 | 数组 哈希表 排序 |