[python 刷题] 739 Daily Temperatures

[python 刷题] 739 Daily Temperatures

题目：

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

这是一道 monotonic stack 的题，翻了一下之前关于 monotonic stack 的笔记，写的不是特别的好，当时看的时候觉得讲明白了，好久不刷题再复习的时候又觉得有点似懂非懂的，把 sack 翻完重新写一下……

这道题其实图解一下看起来就比较简单了，以 temperatures = [73,74,75,71,69,72,76,73] 为例：

对于每一天的天气来说，找到下一个在 y 轴上比它高的数字即可，暴力解就是遍历所有的可能性，时间复杂度为 $O(n^2)$

另一个利用 monotonic stack 的思路如下：

目前正在遍历的值为 temp

• 当 stack 为空，或 temp < stack[-1] 小的时候，进行入栈的操作

• 当 temp > stack[-1] 时，证明当天比 stack[-1] 这天的温度高

  这时候可以进行一个退栈，并更新对应 index 值

完整的走一遍案例：

res 初始化为 [0] * len(temps)

1. 第一天进行一个入栈的操作

   

2. 第二天在对比值的时候，发现 temp 比 stack[-1] 大

   这证明了今天的温度高于 stack[-1] 这一天所在的值，因此进行一个退栈的操作，并且更新对应 index 上的天数为 curr_index - stack[-1].i

   res = [1-0,0,0,0,0,0,0,0]

   完成遍历后继续进行一个入栈的操作

   

3. 第三天进行同样的对比操作

   过程和第二天一样，此时 res = [1,2-1,0,0,0,0,0,0]

   

4. 第四天的情况有些不一样，因为当天的 temp < stack[-1]

   所以当天没有进行退栈的操作

   

5. 第五天的情况也是 temp < stack[-1]

   所以依旧没有退栈，只有入栈的操作

   

   这个时候已经能够看得比较明显，这个栈中保存的值是一个递减的状态

6. 第六天碰到了 temp > stack[-1] 的情况

   这时候按照逻辑进入迭代，当 temp > stack[-1] 的时候，持续性的出栈

   

   res 这里也根据弹出的两个值进行更新：

   res = [1,1,0,5-3,5-4,0,0,0]

   因为图标解释按天数算是 1-indexed based 的，数组时 0-indexed based，这里会有个误差，第六天对应的下标时 5

   可以比较明显看到，此时的 stack 还是一个递减栈

7. 第七天的温度也比 stack[-1] 的温度高

   依旧进行一个出栈，更新对应天数，再入栈的操作：

   

   res = [1,1,0,2,1,7-6,0,0]

   这里画图的时候画错了，案例里面是 75，不过不改了，testcase 跑出来的结果是对的：

   

   所以准贴的说，这题里的 stack 时递减或持平

8. 最后一天不满足退栈的情况，结束循环

   最终 res = [1,1,0,2,1,1,0,0]

   stack 中留下三个值：

   

按照这个逻辑的代码为：

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = []

        for i, temp in enumerate(temperatures):
            while stack and temp > stack[-1][0]:
                stackT, stackI = stack.pop()
                res[stackI] = i - stackI

            stack.append((temp, i))

        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14