Given a list of daily temperatures`T`

, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put`0`

instead. For example, given the list of temperatures`T = [73, 74, 75, 71, 69, 72, 76, 73]`

, your output should be`[1, 1, 4, 2, 1, 1, 0, 0]`

.Note:The length of`temperatures`

will be in the range`[1, 30000]`

. Each temperature will be an integer in the range`[30, 100]`

.

This is a great exercise for **Monotonic Stack**. Monotonic stack is a stack when the items in it are kept in order (monotonically increasing or monotonically decreasing). One of the properties of it is that:

- With a monotonically
**increasing**stack, you can find the first item that is smaller than each item. - With a monotonically
**decreasing**stack, you can find the first item that is larger than each item.

#### Logic

We use monotonically decreasing stack `mono`

. Iterating from the left to the right:

- when we meet an element that is smaller than the top element in
`mono`

, we would push it to`mono`

. - when we meet an element that is larger than the top element in
`mono`

, we pop it.

#### Code

class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: mono,n = [],len(T) ret = [0] * n for i,val in enumerate(T): while mono and val > mono[-1][1]: pre_i,pre_v = mono.pop() ret[pre_i] = i - pre_i mono.append((i,val)) return ret

#### Reference

- https://leetcode.com/problems/daily-temperatures/
- https://medium.com/algorithms-and-leetcode/monotonic-queue-explained-with-leetcode-problems-7db7c530c1d6