题目介绍

复杂度

时间复杂度: O(n), 空间复杂度: O(w)，其中 w 是 T[i] 的可取值的数目。

解题思路

这一题通过栈记录索引，满足 T[stack[-1]] < T[stack[-2]] < …

举个例子：我们反向遍历处理 t=[73，74，75，71，69，72，76，73]。为了清楚 stack 只包含索引 i，但是将把 T[i] 的值用元祖进行记录，例如 (0, 73)。

当 i = 7，stack = [(7, 73)]。ans[i] = 0。
当 i = 6，stack = [(6, 76)]。ans[i] = 0。
当 i = 5，stack = [(5, 72), (6 ,76)]。ans[i] = 1。
当 i = 4，stack = [(4 ,69), (5 ,72), (6 ,76)]。ans[i] = 1。
当 i = 3，stack = [(3 ,71), (5 ,72), (6 ,76)]。ans[i] = 2。
当 i = 2，stack = [(2 ,75), (6 ,76)]。ans[i] = 4。
当 i = 1，stack = [(1 ,74), (2 ,75), (6 ,76)]。ans[i] = 1。
当 i = 0，stack = [(0 ,73), (1 ,74), (2 ,75), (6 ,76)]。ans[i] = 1。

class Solution {
    func dailyTemperatures(_ T: [Int]) -> [Int] {
        var ans = Array(repeating: 0, count: T.count)
        var stack: [(Int, Int)] = []
        for (index, t) in T.enumerated().reversed() {
            while !stack.isEmpty && stack.last!.1 <= t {
                stack.removeLast()
            }
            if !stack.isEmpty {
                ans[index] = stack.last!.0 - index
            }
            stack.append((index, t))
        }
        return ans
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/04/05/DailyTemperatures/