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%