⚡Flashcard Drill➔
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

  1. Maintain a monotonically decreasing stack of indices whose temperatures have not yet found a warmer day.
  2. For each new day, pop every index whose temperature is strictly less than today's -- today is their answer.
  3. The distance i - j is the number of days waited.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems