[Swift]LeetCode496. 下一个更大元素 I | Next Greater Element I

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（/strengthen/）

➤GitHub地址：/strengthen/LeetCode

➤原文地址：/strengthen/p/9805282.html

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

You are given two arrays(without duplicates)nums1andnums2wherenums1’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 numberxinnums1is 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 innums1andnums2are unique.The length of bothnums1andnums2would 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 }