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?
CodePudding user response:
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.