Daily Temperatures

Tips

Problem Type: Monotonic Stack

Problem

Given an array of integers temperatures representing the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example

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

Output: [1, 1, 4, 2, 1, 1, 0, 0]

Solution

JavaScript
Rust

Use a monotonic stack, where i - prevIndex gives us the distance.

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  const n = temperatures.length
  const stack = []
  const result = new Array(n).fill(0)

  for (let i = 0; i < n; i++) {
    while (
      stack.length > 0 &&
      temperatures[stack[stack.length - 1]] < temperatures[i]
    ) {
      const prevIndex = stack.pop()
      result[prevIndex] = i - prevIndex
    }

    stack.push(i)
  }

  return result
}

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

    for (i, temperature) in temperatures.iter().enumerate() {
        while !stack.is_empty() && temperatures[stack[stack.len() - 1]] < *temperature {
            let prev_index = stack.pop().unwrap();
            result[prev_index] = (i - prev_index) as i32;
        }

        stack.push(i);
    }

    result
}

Time Complexity: O(n), where n is the length of the temperatures array. We traverse the temperatures array once, and for each index in the array, there is at most one push and one pop operation.

Space Complexity: O(n), where n is the length of the temperatures array. We need to maintain a monotonic stack to store the indices of the temperatures array.

Problem​

Solution​

Problem

Solution