496. Next Greater Element I
You are given two arrays (without duplicates) nums1
and nums2
where nums1
’s elements are 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, output -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.
Note:
- All elements in
nums1
andnums2
are unique. - The length of both
nums1
andnums2
would not exceed 1000.
# @lc code=start
using LeetCode
function next_greater_element(num1::Vector{Int}, num2::Vector{Int})
stk = Int[]
res = fill(-1, length(num2))
inv_idx = Dict{Int,Int}()
for i in length(num2):-1:1
inv_idx[num2[i]] = i
while !isempty(stk) && stk[end] <= num2[i]
pop!(stk)
end
res[i] = isempty(stk) ? -1 : stk[end]
push!(stk, num2[i])
end
return [res[inv_idx[item]] for item in num1]
end
# @lc code=end
next_greater_element (generic function with 1 method)
This page was generated using DemoCards.jl and Literate.jl.