Solve LeetCode 739 ‘Daily Temperatures’ Using a Monotonic Stack

Problem Description

Given an integer array nums representing daily temperatures, return an array answer where answer[i] is the number of days until a warmer temperature appears after day i; if none, answer[i] = 0.

Constraints

1 ≤ temperatures.length ≤ 10^5

30 ≤ temperatures[i] ≤ 100

Examples

Input: nums = [73,74,75,71,69,72,76,73] Output: [1,1,4,2,1,1,0,0]

Input: nums = [30,40,50,60] Output: [1,1,1,0]

Analysis

The task is equivalent to finding, for each element, the distance to the next greater element on its right. A monotonic increasing stack efficiently solves this in O(n) time.

In a monotonic stack, indices are stored such that the temperatures at those indices are in decreasing order from bottom to top; the top of the stack holds the smallest temperature among the stored indices.

Algorithm

Iterate i from 0 to n‑1.

While the stack is not empty and nums[i] > nums[stack.top()], pop the top index j and set answer[j] = i - j.

Push i onto the stack.

After the loop, any remaining indices in the stack have no warmer day, so their answer stays 0.

Reference Implementations

Java

public int[] dailyTemperatures(int[] nums) {
    int length = nums.length;
    int[] ans = new int[length];
    Stack<Integer> stk = new Stack<>();
    for (int i = 0; i < length; i++) {
        while (!stk.isEmpty() && nums[i] > nums[stk.peek()]) {
            ans[stk.peek()] = i - stk.pop();
        }
        stk.push(i);
    }
    return ans;
}

C++

vector<int> dailyTemperatures(vector<int>& nums) {
    int length = nums.size();
    vector<int> ans(length);
    stack<int> stk;
    for (int i = 0; i < length; i++) {
        while (!stk.empty() && nums[i] > nums[stk.top()]) {
            ans[stk.top()] = i - stk.top();
            stk.pop();
        }
        stk.push(i);
    }
    return ans;
}

Python

def dailyTemperatures(self, nums: List<int>) -> List<int>:
    length = len(nums)
    ans = [0] * length
    stk = []
    for i in range(0, length):
        while stk and nums[i] > nums[stk[-1]]:
            ans[stk[-1]] = i - stk[-1]
            stk.pop()
        stk.append(i)
    return ans

Illustrations