每日温度

Tips

题目类型: 单调栈

题目

请根据每日气温列表, 重新生成一个列表. 对应位置的输出为: 要想观测到更高的气温, 至少需要等待的天数. 如果气温在这之后都不会升高, 请在该位置用 0 来代替.

示例

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

输出: [1, 1, 4, 2, 1, 1, 0, 0]

题解

JavaScript
Rust

使用单调栈, i - prevIndex 即是距离.

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

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

    stack.push(i)
  }

  return res
}

pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
    let n = temperatures.len();
    let mut stack = vec![];
    let mut res = 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();
            res[prev_index] = (i - prev_index) as i32;
        }

        stack.push(i);
    }

    res
}

时间复杂度: O(n), 其中 n 是温度列表的长度. 正向遍历温度列表一遍, 对于温度列表中的每个下标. 最多有一次进栈和出栈的操作.

空间复杂度: O(n), 其中 n 是温度列表的长度. 需要维护一个单调栈存储温度列表中的下标.

题目​

题解​

题目

题解