目录
题目描述
- 题目地址：https://leetcode.cn/problems/next-greater-element-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] 是如上所述的 下一个更大元素 。
解决方法一
解题思路
- 逐个计算nums1中的每个元素值nums [i] 在nums2中对应位置的右边的第一个比 nums1[i]大的元素值。具体地，我们使用如下方法：
- 初始化与nums 1等长的查询数组res
- 遍历nums1中的所有元素，设当前遍历到元素为nums1[i]:
- 从前向后遍历nums2中的元素，直到找到nums2[j] = nums1[i];
- 从j+1开始继续向后遍历，直到找到nums2[k] = nums2[j],其中k>=j+1;
- 如果找到了nums2[k],则将res[i]置为nums2[k],否则将res[i]置为-1.
- 查询数组res即为最终结果。
解题代码
var nextGreaterElement = function(nums1, nums2) {
const m = nums1.length, n = nums2.length;
const res = new Array(m).fill(0);
for (let i = 0; i < m; ++i) {
let j = 0;
while (j < n && nums2[j] !== nums1[i]) {
++j;
}
let k = j + 1;
while (k < n && nums2[k] < nums2[j]) {
++k;
}
res[i] = k < n ? nums2[k] : -1;
}
return res;
};