★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(/strengthen/)
➤GitHub地址:/strengthen/LeetCode
➤原文地址:/strengthen/p/9805282.html
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
You are given two arrays(without duplicates)nums1
andnums2
wherenums1
’s elements are subset ofnums2
. Find all the next greater numbers fornums1
's elements in the corresponding places ofnums2
.
The Next Greater Number of a numberxinnums1
is the first greater number to its right innums2
. 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 innums1
andnums2
are unique.The length of bothnums1
andnums2
would not exceed 1000.
给定两个没有重复元素的数组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。
注意:
nums1
和nums2
中所有元素是唯一的。nums1
和nums2
的数组大小都不超过1000。
16ms
1 class Solution { 2func nextGreaterElement(_ findNums: [Int], _ nums: [Int]) -> [Int] { 34 // 9,8,7,6,5,10 -> 10 is the next greater for all 5 var result = [Int]() 6 var dict = [Int: Int]() 7 var stack = [Int]() 89 for num in nums {10 while !stack.isEmpty && stack.last! < num {11 let last = stack.removeLast()12 dict[last] = num13 }14 15 stack.append(num)16 }17 18 for num in findNums {19 result.append(dict[num] ?? -1)20 }21 22 return result23}24 }
20ms
1 class Solution { 2func nextGreaterElement(_ findNums: [Int], _ nums: [Int]) -> [Int] { 34 var ans = [Int]() 5 var stack = [Int]() 6 var dict = [Int:Int]() 78 for (index, item) in nums.enumerated() { 9 dict[item] = index10 ans.append(0)11 }12 13 for val in nums {14 while stack.count > 0 && val > stack.last! {15 ans[dict[stack.last!]!] = val16 stack.removeLast()17 }18 stack.append(val)19 }20 var newAns = [Int]()21 for val in findNums {22 if let x = dict[val] {23 newAns.append(ans[x]==0 ? -1 : ans[x])24 }25 }26 return newAns27}28 }
24ms
1 class Solution { 2func nextGreaterElement(_ findNums: [Int], _ nums: [Int]) -> [Int] { 3 var dict = [Int:Int]() 4 var stack = [Int]() 56 for num in nums { 7 while stack.count > 0 && stack.last! < num { 8 dict[stack.popLast()!] = num 9 }10 stack.append(num)11 }12 13 return findNums.map { dict[$0] ?? -1 }14}15 }
32ms
1 class Solution { 2func findindex(_ nums: [Int], _ search: Int, _ count: Int) -> Int { 3 for i in 0..<count { 4 if (nums[i] == search) { 5 return i 6 } 7 } 8 return -1 9}10func nextGreaterElement(_ findNums: [Int], _ nums: [Int]) -> [Int] {11 var output = [Int]()12 var index = -113 var flag = false14 let count = nums.count15 for i in findNums {16 index = findindex(nums, i, count)17 if (index != (count-1)) {18 flag = false19 for j in nums[index..<count] {20 if (i<j) {21output.append(j)22flag = true23break24 }25 }26 if (!flag) {27 output.append(-1)28 }29 } else {30 output.append(-1)31 }32 }33 return output34}35 }
40ms
1 class Solution { 2func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] { 3 var dict = [Int: Int]() 45 for (index, num) in nums2.enumerated() { 6 dict[num] = index 7 } 8 9 var result: [Int] = []10 for num in nums1 {11 var index: Int = dict[num]!12 var max: Int = -113 while index < nums2.count {14 if num < nums2[index] {15 max = nums2[index]16 break17 }18 19 index += 120 }21 22 result.append(max)23 }24 25 return result26}27 }
44ms
1 class Solution { 2func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] { 3 var nextGreater = [Int]() 4 var stack = [Int]() 5 var dict = [Int:Int]() 6 7 for num in nums2 { 8 while !stack.isEmpty && num > stack.last! { 9 dict[stack.removeLast()] = num10 }11 12 stack.append(num)13 }14 15 for num in nums1 {16 nextGreater.append(dict[num] ?? -1)17 }18 19 return nextGreater20}21 }
68ms
1 class Solution { 2func nextGreaterElement(_ findNums: [Int], _ nums: [Int]) -> [Int] { 3 var result: [Int] = [] 4 var item = findNums.count-1 5 while item >= 0 { 6 var itemResult = -1 7 var itemFinded = -1 8 for index in 0..<nums.count { 9 if findNums[item] == nums[index] {10itemFinded = index11 }12 if findNums[item] < nums[index] && itemFinded != -1 {13itemResult = nums[index]14break15 }16 }17 result.insert(itemResult, at: 0)18 item = item - 119 }20 return result21 }22 }
72ms
1 class Solution { 2func nextGreaterElement(_ findNums: [Int], _ nums: [Int]) -> [Int] { 3var res:[Int] = [] 4 for i in 0..<findNums.count { 5 for j in 0..<nums.count{ 6 if findNums[i] == nums[j] { 7 for k in j...nums.count-1 { 8if (findNums[i] < nums[k]) { 9 res.append(nums[k])10 break11}else if (k == (nums.count-1)){12 res.append(-1)13}14 }15 16 }17 }18 }19 return res20}21 }
72ms
1 class Solution { 2func nextGreaterElement(_ nums1: [Int], _ nums2: [Int]) -> [Int] { 3 var nextGreater = [Int]() 4 var stack = [Int]() 5 var dict = [Int:Int]() 6 7 for num in nums2 { 8 while !stack.isEmpty && num > stack.last! { 9 dict[stack.removeLast()] = num10 }11 12 stack.append(num)13 }14 15 for num in nums1 {16 nextGreater.append(dict[num] ?? -1)17 }18 19 return nextGreater20}21 }