# 739. Daily Temperatures

{% embed url="<https://leetcode.com/problems/daily-temperatures/>" %}

看到就觉得眼熟，跟 sliding window 那道需要用特殊数据结构的难题 [239. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/) 一样，可以用`monotonic stack`做。

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

```python
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掉，肯定用不到了（因为是倒序找）。

```python
    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
```
