[Leetcode]739. Daily Temperatures

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

Monotonic stack 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

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments