739. Daily Temperatures

Loading...LeetCode

看到就觉得眼熟，跟 sliding window 那道需要用特殊数据结构的难题 239. Sliding Window Maximum 一样，可以用monotonic stack做。

维护一个单调递减的 stack（如果是倒序遍历的话可以做单调递增），遇到比最右侧元素大的值就开始pop，一直pop到可以继续维持单调为止。每次pop出来的元素即找到了下一个wamer day（当前新元素），可以更新进结果，

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        res = [0 for _ in range(len(T))]
        stack = collections.deque([])
        
        for i in range(len(T)):
            while stack and T[i] > T[stack[-1]]:
                    small = stack.pop()
                    res[small] = i - small
            stack.append(i)
            
        return res

Discussion 里看到另一个monotonic stack的写法，但思路是倒序遍历更新 result 数列，挺不一样的。

这里维护的 stack 代表已经遍历过的元素，对于每个result，都在stack里找最右侧大于它的，然后更新进去，小于当前的就直接pop掉，肯定用不到了（因为是倒序找）。

    def dailyTemperatures(self, T):
        res = [0] * len(T)
        stack = []
        
        for index in range(len(T)-1, -1, -1):
            while stack and T[stack[-1]] <= T[index]:
                stack.pop()
            res[index] = stack[-1] - index if stack else 0
            stack.append(index)
            
        return res