[Swift]LeetCode503. 下一个更大元素 II | Next Greater Element II

概述Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first gre

Given a circular array (the next element of the last element is the first element of the array),print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array,which means you Could search circularly to find its next greater number. If it doesn‘t exist,output -1 for this number.

Example 1:

input: [1,2,1]Output: [2,-1,2]Explanation: The first 1‘s next greater number is 2; 
The number 2 can‘t find next greater number; 
The second 1‘s next greater number needs to search circularly,which is also 2. 

Note: The length of given array won‘t exceed 10000.

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: [1,1]输出: [2,2]解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

注意: 输入数组的长度不会超过 10000。

300ms

 1 class Solution { 2     func nextGreaterElements(_ nums: [Int]) -> [Int] { 3         if nums.isEmpty { return [] } 4         let n = nums.count 5         var result = [Int](repeating: -1,count: n) 6         var stack = [Int]() 7          8         for i in 0..<2 * n { 9             while !stack.isEmpty && nums[stack.last!] < nums[i % n] {10                 let top = stack.removeLast()11                 result[top] = nums[i % n]12             }13             if i < n {14                 stack.append(i)15             }16         }17         18         return result19     }20 }

316ms

 1 class Solution { 2     func nextGreaterElements(_ nums: [Int]) -> [Int] { 3         var res = [Int](repeating: -1,count: nums.count) 4         var s = [Int]() 5         //5 3 2 1 4 6         // 7         for i in 0..<nums.count*2 { 8             if s.isEmpty || nums[s[s.count-1]] > nums[i%nums.count] { 9                 s.append(i%nums.count)10             } else {11                 while !s.isEmpty && nums[s[s.count-1]] < nums[i%nums.count] {12                     res[s[s.count-1]] = nums[i%nums.count]13                     s.removeLast()14                 }15                 s.append(i%nums.count)16             }17         }18         return res19     }20 }       

320ms

 1 class Solution { 2     func nextGreaterElements(_ nums: [Int]) -> [Int] { 3      4     var stack : [(val : Int,index : Int)] = [] 5     var result : [Int] = [Int](repeating: -1,count: nums.count) 6      7     for (index,val) in nums.enumerated(){ 8         while !stack.isEmpty && stack.last!.val < val{ 9             let removed = stack.removeLast()10             result[removed.index] = val11         }12         stack.append((val: val,index: index))13     }14     15     for val in nums{16         while !stack.isEmpty && stack.last!.val < val{17             let removed = stack.removeLast()18             result[removed.index] = val19         }20     }21     return result22    }23 }

328ms

 1 class Solution { 2     func nextGreaterElements(_ nums: [Int]) -> [Int] { 3         var stack = [(Int,Int)]() 4         var result = Array(repeating: -1,count: nums.count) 5          6         for i in 0..<nums.count * 2 { 7             let index = i % nums.count 8             let this = nums[index] 9             10             while !stack.isEmpty && this > stack.last!.1 {11                 let v = stack.removeLast()12                 result[v.0] = this13             }14             stack.append((index,this))15         }16         17         return result18     }19 }

380ms

 1 class Solution { 2  3     func nextGreaterElements(_ nums: [Int]) -> [Int] { 4         if nums.count == 0 { 5             return [] 6         } 7         var result = Array(repeating: -1,count: nums.count) 8         var stack = [Int]() 9         let length = nums.count10         for i in 0..<(2 * length)11         {12             let index = i % length13             let current = nums[index]14 15             while !stack.isEmpty && current > nums[stack.last!] {16                 result[stack.popLast()!] = nums[index]17             }18 19             // 第二次循环时，不重复处理20             if i < length {21                 stack.append(index)22             }23         }24         return result25     }26 }

432ms

 1 class Solution { 2  3     struct IntegerStack { 4         typealias Element = Int 5  6         var isEmpty: Bool { return stack.isEmpty } 7         var size: Int { return stack.count } 8         var peek: Element? { return stack.last } 9 10         private var stack = [Element]()11 12         mutating func push(_ newElement: Element) {13             stack.append(newElement)14         }15 16         mutating func pop() -> Element? {17             return stack.popLast()18         }19     }20 21     func nextGreaterElements(_ nums: [Int]) -> [Int] {22         if nums.count == 0 {23             return []24         }25         var result = Array(repeating: -1,count: nums.count)26         var stack = IntegerStack()27         stack.push(0)28         var i = 129         let length = nums.count30         while i < 2 * length - 1 && !stack.isEmpty {31             let index = i % length32             let current = nums[index]33             if current > nums[stack.peek!] {34                 result[stack.pop()!] = current35                 if stack.isEmpty {36                     stack.push(index)37                     i += 138                 }39             } else {40                 stack.push(index)41                 i += 142             }43         }44 45         return result46     }47 }

536ms

 1 class Solution { 2     func nextGreaterElements(_ nums: [Int]) -> [Int] { 3     var result=[Int]() 4          for (index,value) in nums.enumerated(){ 5             var i=index+1 6           while i<nums.count{ 7               if value<nums[i]{ 8                   result.append(nums[i]) 9                   break10               }11               i+=112           }13               var j=014              while result.count<index+1 {15                 if value<nums[j]{16                   result.append(nums[j])17                   break18               }19             else if j==index{20                 result.append(-1)21                   break22               }23              j+=1                   24             }25          }26        return result27       }28 }

600ms

 1 class Solution { 2     func nextGreaterElements(_ nums: [Int]) -> [Int] { 3     var result=[Int]() 4          5          for (index,value) in nums.enumerated(){ 6              var  i=(index+1)==nums.count ? 0 : index+1 7               result.append(-1) 8              while i != index { 9                 if value<nums[i]{10                 result[index]=nums[i]11                   break12                 }13              else{14                  i+=115             if i==nums.count{16                  i=017                  } 18                }  19             }20          }21         return result22     }23 }

624ms

 1 class Solution { 2     func nextGreaterElements(_ nums: [Int]) -> [Int] { 3         let t = nums + nums 4         let r = helper(t,t) 5         var results = [Int]() 6          7         for i in 0..<nums.count { 8             let this = r[i] 9             if this == -1 {10                 results.append(r[nums.count + i])11             } else {12                 results.append(this)13             }14         }15         16         return results17     }18     19     func helper(_ findNums: [Int],_ nums: [Int]) -> [Int] {20         var result = Array(repeating: -1,count: findNums.count)21         var dict = [Int: [Int]]()22         23         for (i,num) in findNums.enumerated() {24             if dict[num] == nil {25                 dict[num] = [i]26             } else {27                 dict[num]?.append(i)28             }29         }30         31         for key in dict.keys {32             dict[key]?.reverse()33         }34         35         var stack = [Int]()36         for num in nums {37             while !stack.isEmpty && stack.last! < num {38                 let c = stack.removeLast()39                 40                 if let i = dict[c]?.removeLast() {41                     result[i] = num42                 }43             }44             stack.append(num)45         }46         47         return result48     }49 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode503. 下一个更大元素 II | Next Greater Element II全部内容，希望文章能够帮你解决[Swift]LeetCode503. 下一个更大元素 II | Next Greater Element II所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。