给你两个 没有重复元素 的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出 -1 。
示例
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ,你无法在第二个数组中找到下一个更大的数字,因此输出 -1 。
对于 num1 中的数字 1 ,第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ,第二个数组中没有下一个更大的数字,因此输出 -1 。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ,第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ,第二个数组中没有下一个更大的数字,因此输出 -1 。
题解
利用栈找下一个大数字
先建立一个栈,放入 nums2 第一个数
stack = [1]
遍历 nums2 拿到3,比栈顶 1 要大,推出 1,记录 {1: 3},推入3
stack = [3]
遍历下一个数4, ,比栈顶 3 要大,推出 3,记录 {1: 3, 3: 4},推入4
stack = [4]
遍历下一个数2,比栈顶 4 小,推入 2
遍历结束后,再遍历 nums1,获取记录表上的值,没有则是 - 1,得到 [-1,3,-1]
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var nextGreaterElement = function(nums1, nums2) {
const map = {}
const stack = [nums2[0]]
const res = []
for (let i = 1; i < nums2.length; i++) {
while(nums2[i] > stack[stack.length - 1] && stack.length > 0) {
const n = stack.pop()
map[n] = nums2[i]
}
stack.push(nums2[i])
}
for (let i = 0; i < nums1.length; i++) {
if (map[nums1[i]] === undefined) {
res.push(-1)
} else {
res.push(map[nums1[i]])
}
}
return res
};
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/next-greater-element-i
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。