【Leetcode Daily】739每日温度

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个数组代表一组温度，求每个温度与下一次比当前温度大的天数之差。

思路分享

• 对于每个元素想要找各自的下一个更大或者更小的情况，可以通过单调栈来比较便利地解决。

• 所谓单调栈，就是维护一个栈的单调性，使得其从栈顶到栈底是递增或者递减的关系。也就是只要维护已遍历的部分中的最大或者最小值（枚举的思路也有些相近）。

• 具体的做法大致两个方法，但都是一个思路，就是去除无用信息，让程序尽快判断出

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stk = [] # 这个栈是存右侧的最大值下标的
        right = [0] * n
        for i in range(n-1, -1, -1):
            t = temperatures[i]
            while stk and temperatures[stk[-1]] <= t:
                stk.pop()
            if stk:
                right[i] = stk[-1] - i
            stk.append(i) # 虽然当前的数值不一定大于栈顶，但可能比左侧大，遵循最近原则需要入栈
        return right


        # 下面是从左往右
        # n = len(temperatures)
        # stk = []
        # left = [0] *n
        # for i, x in enumerate(temperatures):
        #     while stk and temperatures[stk[-1]] < x:
        #         j = stk.pop() # 栈内的是没有匹配的项，遇到大项就开始匹配。
        #         left[j] = i - j
        #     stk.append(i)
        
        # return left