Leetcode 739: Daily Temperatures when to use a monotic stack?

Question

I was working on https://leetcode.com/problems/daily-temperatures/ and after struggling I realized a monotonically decreasing stack helps me solve the problem. I've copied over the question below.

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead. My solution is below.

 def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        mono_decreasing_stack = []
        N = len(temperatures)
        temps = [0] * N
        for i in reversed(range(0, N)):
            temp = temperatures[i]
            while mono_decreasing_stack and temp >= temperatures[mono_decreasing_stack[-1]]:
                # maintain the monotonically decreasing stack property
                mono_decreasing_stack.pop()
               # do something with the popped element
            if mono_decreasing_stack:
                temps[i] = mono_decreasing_stack[-1] - i
            mono_decreasing_stack.append(i)
        return temps

Although in this problem a monotonically decreasing stack is helpful to store and retrieve the "next" warmer day, I realize in other problems a monotonically increasing stack is more helpful. Are there some general rules I can apply to decide whether to use a monotonically decreasing or increasing stack? Am I right in that if the problem instead asked for the number of days I have to wait after the ith day to get a colder temperature, I would use a monotonically increasing stack?

Answer 1

You are not using the value from mono_decreasing_stack.pop(), this is the index where you have a lower value than the current value in a monotonic decreasing stack and you need to compute offset as current_index - popped_index

Also not sure why you would want to traverse from the end. You could start from beginning and build a monotonic decreasing stack with the same condition you have i.e. temp > temperatures[mono_decreasing_stack[-1]]

The modified code would be:

def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    mono_decreasing_stack = []
    N = len(temperatures)
    temps = [0] * N
    for i in range(N):
        temp = temperatures[i]
        while mono_decreasing_stack and temp > temperatures[mono_decreasing_stack[-1]]:
            # maintain the monotonically decreasing stack property
            idx = mono_decreasing_stack.pop()
            # do something with the popped element
            temps[idx] = i - idx
        mono_decreasing_stack.append(i)
    return temps

And you are right about number of days I have to wait after the ith day to get a colder temperature, I would use a monotonically increasing stack? Just change > sign to < sign in while condition.