[Swift]LeetCode739.每日温度|DailyTemperatures

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10522255.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高的天数。如果之后都不会升高，请输入 0来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的都是 [30, 100] 范围内的整数。

484ms

 1 class Solution {
 2     func dailyTemperatures(_ T: [Int]) -> [Int] {
 3         let n = T.count
 4         var res = Array(repeating: 0, count: n)
 5         for i in (0..<n).reversed() {
 6             var j = i + 1
 7             while j < n, T[j] <= T[i]  {
 8                 if res[j] > 0 {
 9                     j  += res[j]
10                 } else {
11                     j = n
12                 }
13             }
14             if j < n {
15                 res[i] = j - i
16             }
17         }
18         return res
19     }
20 }

488ms

 1 class Solution {
 2     func dailyTemperatures(_ T: [Int]) -> [Int] {
 3         var result = [Int](repeating: 0, count: T.count)
 4         var stack = [Int]()
 5         stack.append(0)
 6         for i in 1..<T.count {
 7             while let last = stack.last, T[last] < T[i] {
 8                 stack.removeLast()
 9                 result[last] = i - last
10             }
11             stack.append(i)
12         }
13         return result
14     }
15 }

556ms

 1 class Solution {
 2     func dailyTemperatures(_ T: [Int]) -> [Int] {
 3   var result = Array(repeating: 0, count: T.count)
 4   var tempStorage = Array(repeating: Int.max, count: 101)
 5 
 6   for i in 0..<T.count {
 7         tempStorage[T[i]] = i
 8   }
 9         
10   var minGreaterThanI = Int.max
11   
12   for currentIndex in (0..<T.count).reversed() {
13     let t = T[currentIndex]
14       
15     if currentIndex != tempStorage[t] {
16         tempStorage[t] = currentIndex
17     }
18       
19     for temp in t+1..<101 {
20       let indexFromList = tempStorage[temp]
21       if indexFromList > currentIndex && indexFromList < minGreaterThanI {
22           minGreaterThanI = indexFromList
23       }
24     }
25     
26       if minGreaterThanI != Int.max {
27           result[currentIndex] = minGreaterThanI - currentIndex
28           minGreaterThanI = Int.max
29       }
30   }
31   
32   return result
33   }
34 }

796ms

 1 class Solution {
 2     func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
 3         guard temperatures.count > 1 else { return [0] }
 4 
 5         var result = [Int](repeating: 0, count: temperatures.count)
 6 
 7         var stack = [(index: Int, temperature: Int)]()
 8 
 9         for (index, curTemperature) in temperatures.enumerated() {
10 
11             while stack.count > 0 {
12                 var last = stack.last!
13                 if curTemperature > last.temperature {
14                     last = stack.removeLast()
15                     result[last.index] = index - last.index
16                 } else {
17                     break
18                 }
19             }
20 
21             stack.append((index, curTemperature))
22         }
23 
24         return result
25     }
26 }

832ms

 1 class Solution {
 2     
 3     struct Temperature {
 4         var temperature = 0
 5         var index = 0
 6     }
 7     
 8     struct Stack<Temperature> {
 9         private var temperatures = [Temperature]()
10         mutating func push(_ item:Temperature){
11             self.temperatures.append(item)
12         }
13         
14         mutating func pop()->Temperature?{
15             return self.temperatures.popLast()
16         }
17         
18         func isEmpty() -> Bool {
19             return self.temperatures.isEmpty
20         }
21         
22         func peek() -> Temperature? {
23            return self.temperatures.last
24         }
25     }
26     
27     func dailyTemperatures(_ T: [Int]) -> [Int] {
28         var resc:[Int] = Array.init(repeating: 0, count: T.count)
29         var stack:Stack = Stack<Temperature>()
30         
31         for (index,temperature) in T.enumerated() {
32             let tempr = Temperature.init(temperature: temperature, index: index)
33            
34             while let peek = stack.peek(), peek.temperature < temperature {
35                 resc[peek.index] = index - peek.index
36                 stack.pop()
37             }
38             stack.push(tempr)
39         }
40         return resc
41     }
42 }