Stage 1: Foundations·Stack & Queue Fundamentals

Medium#7397 min readMonotonic StackArraysLeetCode

Daily Temperatures

Monotonic decreasing stack

Your first monotonic stack! ‘Next greater element’ pattern.

Published Apr 15, 2026

Problem

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

If there is no future day for which this is possible, answer[i] = 0.

Input

temperatures = [73,74,75,71,69,72,76,73]

Output

[1,1,4,2,1,1,0,0]

Input

temperatures = [30,40,50,60]

Output

[1,1,1,0]

Intuition

For each day, we want the next greater element to the right. The brute force version is simple: for each index, scan forward until you find a warmer day. But that repeats the same work over and over.

The better view is to keep the days whose answer is still unresolved. If the current temperature is warmer than the unresolved day on the top of the stack, then the current day is exactly the answer for that older day.

That means the stack should be monotonically decreasing by temperature. New temperatures pop smaller ones until the stack is valid again.

Approach

Brute Force

TimeO(n²)

SpaceO(1)

For each day i, scan to the right until you find a warmer temperature. Record the distance, or 0 if no such day exists.

It is correct, easy to reason about, and too slow for the real constraints.

impl Solution {
    pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
        let n = temperatures.len();
        let mut answer = vec![0; n];

        for i in 0..n {
            let mut j = i + 1;
            while j < n && temperatures[j] <= temperatures[i] {
                j = 1;
            }
            if j < n {
                answer[i]= (j - i) as i32;
            }
        }

        answer
    }
}

Rust · runnable

function dailyTemperatures(temperatures: number[]): number[] {
  const answer = new Array<number>(temperatures.length).fill(0);

  for (let i = 0; i < temperatures.length; i++) {
    let j= i + 1;
    while (j < temperatures.length && temperatures[j] <= temperatures[i]) {
      j++;
    }
    if (j < temperatures.length) answer[i]= j - i;
  }

  return answer;
}

TypeScript · runnable

Monotonic Decreasing Stack

TimeO(n)

SpaceO(n)

Recommended

Store unresolved day indices in a decreasing stack of temperatures. When a warmer day arrives, pop every colder index and fill its answer with the distance to the current day.

Each index enters the stack once and leaves once, so the total work is linear.

impl Solution {
    pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
        let n = temperatures.len();
        let mut answer = vec![0; n];
        let mut stack: Vec<usize> = Vec::with_capacity(n);

        for i in 0..n {
            while let Some(&j) = stack.last() {
                if temperatures[i] > temperatures[j] {
                    stack.pop();
                    answer[j] = (i - j) as i32;
                } else {
                    break;
                }
            }
            stack.push(i);
        }

        answer
    }
}

Rust · runnable

function dailyTemperatures(temperatures: number[]): number[] {
  const answer = new Array<number>(temperatures.length).fill(0);
  const stack: number[] = [];

  for (let i = 0; i < temperatures.length; i++) {
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const j = stack.pop()!;
      answer[j] = i - j;
    }
    stack.push(i);
  }

  return answer;
}

TypeScript · runnable

Language notes:

Rust — store indices, not temperatures. The answer is a distance, and indices let you compute it directly.
TypeScript — the stack can hold raw indices; temperatures[stack[stack.length - 1]] is the unresolved day at the top.

Trace

Running the monotonic stack on [73,74,75,71,69,72,76,73]:

i	temp	stack before	pops	answer updates	stack after
0	73	[]	—	—	[0]
1	74	[0]	pop 0	answer[0] = 1	[1]
2	75	[1]	pop 1	answer[1] = 1	[2]
3	71	[2]	—	—	[2, 3]
4	69	[2, 3]	—	—	[2, 3, 4]
5	72	[2, 3, 4]	pop 4, pop 3	answer[4] = 1, answer[3] = 2	[2, 5]
6	76	[2, 5]	pop 5, pop 2	answer[5] = 1, answer[2] = 4	[6]
7	73	[6]	—	—	[6, 7]

The unresolved stack shrinks exactly when a warmer day appears.

Edge cases

Strictly decreasing temperatures — the stack grows to n and the answer stays all zeroes.
Equal temperatures — not warmer, so they stay on the stack until a strictly larger value appears.
Repeated plateaus — every index still gets resolved independently because the stack stores indices, not values.

💡

Tip

This is the same shape as #496 Next Greater Element. The only difference is the payload: there, you return the warmer value; here, you return the distance to it.

Takeaway

Monotonic stacks are how you answer "next greater/smaller" queries in one pass. The stack holds unresolved items in sorted order, and each new item resolves a suffix of them.

If a brute force scan is repeatedly walking the same suffix, there is probably a monotonic stack hiding in the problem.

Easy#496

Next Greater Element I

The basic pattern. Process right to left, stack holds candidates.

Medium#150

Evaluate Reverse Polish Notation

Stack as an accumulator. This pattern scales to expression parsing.

Medium#853

Car Fleet

Stack with a physical intuition — cars merge when a faster one catches a slower one.