Stack

LeetCode 739

LeetCode #739Difficulty: MediumNeetCode 150

LeetCode 739: Daily Temperatures

LeetCode

Given an array of integers temperatures, return an array answer such that answer[i] is the number of days you have to wait for a warmer temperature.

Problem Description

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 `i-th` day to get a warmer temperature. If there is no future day for which this is possible, keep `answer[i] == 0` instead.

Examples:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Constraints:
  • 1 <= temperatures.length <= 10^5
  • 30 <= temperatures[i] <= 100

Core Mental Model

A Monotonic Decreasing Stack stores day indices whose warmer day has not yet been found, ordered from highest to lowest temperature. When we encounter day `curr` with temperature `T[curr]`: As long as `T[curr]` is greater than temperature at top of stack, we popped it and record `days = curr - top`. Then we push `curr` onto stack.

Formal Loop Invariant

Invariant: The stack strictly maintains temperatures in non-increasing order. Every popped element is matched with its immediate next warmer day in O(1) amortized time.

Key Architectural Takeaway:

Each index is pushed at most once and popped at most once, yielding strictly O(N) total runtime.

Asymptotic Complexity Analysis

Time ComplexityO(N) Aggregate accounting: 2N total push/pop operations.
Space ComplexityO(N) Stores indices on the stack.

Bottleneck: Naive comparisons take O(N²). Monotonic stack skips re-checks.

Edge Cases & Screener Traps

  • Strictly descending temperatures
  • All identical values