NeetCode #355LC-739MediumStackNC 150NC 250
← Back to All Problems#355 · #739 · Daily Temperatures(每日温度)
📌 Problem Statement & Constraints
Given an array of daily temperatures, return an array where
answer[i] is the number of days you must wait after day i for a warmer temperature. If no warmer day exists, answer[i] is 0. Constraints: 1 <= temperatures.length <= 10^5, 30 <= temperatures[i] <= 100.💡 Core Algorithmic Approaches
- Maintain a monotonically decreasing stack of indices whose temperatures have not yet found a warmer day.
- For each new day, pop every index whose temperature is strictly less than today's -- today is their answer.
- The distance
i - jis the number of days waited. - Indices left on the stack never find a warmer day, so their answer stays 0.
💻 Benchmark Python3 Implementation
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
res = [0] * n
st = [] # indices with unresolved answers
for i, t in enumerate(temperatures):
while st and temperatures[st[-1]] < t:
j = st.pop()
res[j] = i - j # days waited
st.append(i)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Using
<=in the comparison: a day with an equal temperature is not warmer, so the strict comparison is required. - Storing temperatures instead of indices: you need the index to compute the distance.
- Returning the temperatures rather than the day counts: the answer is
i - j. - Initialising the answer with a large sentinel: the required default is 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.