DSA Patterns (Multi-Lang)•Part 4: Stacks, Queues & Monotonic Stacks (29 - 36)
Daily Temperatures.
In Simple Words:
Monotonic Decreasing Stack storing indices. When today's temperature exceeds temperatures[stack.top], pop and record distance: res[prevIdx] = i - prevIdx.
- Time: $O(N)$ | Space: $O(N)$
Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++
Switch tabs or choose Alldef dailyTemperatures(temperatures: list[int]) -> list[int]:
res = [0] * len(temperatures)
stack = [] # stores indices
for i, t in enumerate(temperatures):
while stack and t > temperatures[stack[-1]]:
prev = stack.pop()
res[prev] = i - prev
stack.append(i)
return res