代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
You are given two integer arrays nums1
and nums2
both of unique elements, where nums1
is a subset of nums2
.
Find all the next greater numbers for nums1
's elements in the corresponding places of nums2
.
The Next Greater Number of a number x
in nums1
is the first greater number to its right in nums2
. If it does not exist, return -1
for this number.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1] Explanation: For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1. For number 1 in the first array, the next greater number for it in the second array is 3. For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4] Output: [3,-1] Explanation: For number 2 in the first array, the next greater number for it in the second array is 3. For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Constraints:
1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1
and nums2
are unique.nums1
also appear in nums2
.Follow up: Could you find an
O(nums1.length + nums2.length)
solution?
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
mp = {}
stk = []
for num in nums2:
while stk and stk[-1] < num:
mp[stk.pop()] = num
stk.append(num)
return [mp.get(num, -1) for num in nums1]
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Deque<Integer> stk = new ArrayDeque<>();
Map<Integer, Integer> mp = new HashMap<>();
for (int num : nums2) {
while (!stk.isEmpty() && stk.peek() < num) {
mp.put(stk.pop(), num);
}
stk.push(num);
}
int n = nums1.length;
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
ans[i] = mp.getOrDefault(nums1[i], -1);
}
return ans;
}
}
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var nextGreaterElement = function (nums1, nums2) {
let stk = [];
let nextGreater = {};
for (let num of nums2) {
while (stk && stk[stk.length - 1] < num) {
nextGreater[stk.pop()] = num;
}
stk.push(num);
}
return nums1.map(e => nextGreater[e] || -1);
};
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> stk;
unordered_map<int, int> mp;
for (int num : nums2)
{
while (!stk.empty() && stk.top() < num)
{
mp[stk.top()] = num;
stk.pop();
}
stk.push(num);
}
vector<int> ans;
for (int num : nums1) ans.push_back(mp.count(num) ? mp[num] : -1);
return ans;
}
};
func nextGreaterElement(nums1 []int, nums2 []int) []int {
var stk []int
mp := make(map[int]int)
for _, num := range nums2 {
for len(stk) > 0 && stk[len(stk)-1] < num {
mp[stk[len(stk)-1]] = num
stk = stk[:len(stk)-1]
}
stk = append(stk, num)
}
var ans []int
for _, num := range nums1 {
val, ok := mp[num]
if !ok {
val = -1
}
ans = append(ans, val)
}
return ans
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。