739. Daily Temperatures

739. Daily Temperatures

题目描述

Given a list of daily temperatures, produce a list 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 0 instead.

For example, given the list temperatures = [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.

例如,每日温度=[73,74,75,71,69,72,76,73],你的输出应该是[1,1,4,2,1,1,0,0]。

注:温度的长度范围为[1,30000]。
每个温度将是范围内的整数[30,100]。

解题思路

采用Stack + tuple的方式
建立元祖代表下标和温度,使用Array代替Stack
遍历温度列表,将下标和温度压栈。
循环判断栈顶温度是否大于当前温度,如果大于则出栈,否则停止循环。
通过上述操作维护了一个递增栈。

代码

1
2
3
4
5
6
7
8
9
10
11
12
func dailyTemperatures(_ temperatures: [Int]) -> [Int] {
var stack = [(index: Int, value: Int)]()
var ans = Array(repeating: 0, count: temperatures.count)
for (i, t) in temperatures.enumerated() {
while !stack.isEmpty && stack.last!.value < t {
let top = stack.removeLast()
ans[top.index] = i - top.index
}
stack.append((index: i,value: t))
}
return ans
}
0%