Abnerの技术小栈
0%

LeetCode.739 - 每日温度

发表于 更新于 分类于

题目描述

请根据每日气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/daily-temperatures

解题思路（不通过）

先遍历温度列表，在循环中再次遍历温度列表
判断当日温度后若干天的温度，是否比当日温度高
是则插入waitDays，不是则寻找下一个
若内遍历结束仍没有，则waitDays插入0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    func dailyTemperatures(_ T: [Int]) -> [Int] {
        
        var waitDays = [Int]()
        var temperatures = T
        
        for t in temperatures {
            
            // 遍历第一天以外的温度
            temperatures.removeFirst()
            var hasHigherTemp = false
            for index in temperatures.indices {
                let otherT = temperatures[index]
                if (otherT > t) {
                    hasHigherTemp = true
                    waitDays.append(index+1)
                    break
                }
                
            }
            
            // 判断是否有更高温度
            if (!hasHigherTemp) {
                waitDays.append(0)
            }
        }
        
        return waitDays
        
    }
}

问题分析：
时间复杂度：O(n^2)

算法优化（单调栈）

遍历每日温度，维护一个单调栈（单调递减栈）

若栈为空，或者当日温度小于或等于栈顶温度，则直接入栈
反之，若当日温度大于栈顶温度，则说明栈顶的升温日已经找到了，则将栈顶元素出栈，计算其与当日温度差即可
⚠️ 题目要求的是升温的天数，因此栈中应该存下标而不是温度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    func dailyTemperatures(_ T: [Int]) -> [Int] {
        
        var waitDays: [Int] = Array(repeating: 0, count: T.count)
        var stack: [Int] = []
        
        for now in 0 ..< T.count {
           
            // 当栈不为空 && 当日温度>栈顶温度，即找到index的升温日，则将栈顶温度移除且储存对应升温天数
            while let last = stack.last, T[now] > T[last] {
                stack.removeLast()
                waitDays[last] = now - last // 下标差
            }
            
            // 当栈为空 || 当日温度<栈顶温度，入栈
            stack.append(now)
            
        }

        return waitDays
        
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

官方解释

https://www.bilibili.com/video/BV1ov411z7rM?from=search&seid=11178657533565450143