Question

剑指 Offer II 038. 每日温度

题目描述

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

 

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

 

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

 

注意：本题与主站 739 题相同： https://leetcode.cn/problems/daily-temperatures/

解法

方法一：单调栈

单调栈常见模型：找出每个数左/右边离它最近的且比它大/小的数。模板：

stk = []
for i in range(n):
  while stk and check(stk[-1], i):
    stk.pop()
  stk.append(i)

class Solution:
  def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    ans = [0] * len(temperatures)
    stk = []
    for i, t in enumerate(temperatures):
      while stk and temperatures[stk[-1]] < t:
        j = stk.pop()
        ans[j] = i - j
      stk.append(i)
    return ans

class Solution {
  public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] ans = new int[n];
    Deque<Integer> stk = new ArrayDeque<>();
    for (int i = 0; i < n; ++i) {
      while (!stk.isEmpty() && temperatures[stk.peek()] < temperatures[i]) {
        int j = stk.pop();
        ans[j] = i - j;
      }
      stk.push(i);
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> ans(n);
    stack<int> stk;
    for (int i = 0; i < n; ++i) {
      while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
        ans[stk.top()] = i - stk.top();
        stk.pop();
      }
      stk.push(i);
    }
    return ans;
  }
};

func dailyTemperatures(temperatures []int) []int {
  ans := make([]int, len(temperatures))
  var stk []int
  for i, t := range temperatures {
    for len(stk) > 0 && temperatures[stk[len(stk)-1]] < t {
      j := stk[len(stk)-1]
      ans[j] = i - j
      stk = stk[:len(stk)-1]
    }
    stk = append(stk, i)
  }
  return ans
}

function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const res = new Array(n);
  const stack = [];
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length !== 0 && temperatures[stack[stack.length - 1]] <= temperatures[i]) {
      stack.pop();
    }
    res[i] = stack.length === 0 ? 0 : stack[stack.length - 1] - i;
    stack.push(i);
  }
  return res;
}

impl Solution {
  pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
    let n = temperatures.len();
    let mut res = vec![0; n];
    let mut stack = Vec::new();
    for i in (0..n).rev() {
      while !stack.is_empty() && temperatures[*stack.last().unwrap()] <= temperatures[i] {
        stack.pop();
      }
      res[i] = if stack.is_empty() { 0 } else { (stack.last().unwrap() - i) as i32 };
      stack.push(i);
    }
    res
  }
}

方法二

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

class Solution {
  public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    Deque<Integer> stk = new ArrayDeque<>();
    int[] ans = new int[n];
    for (int i = n - 1; i >= 0; --i) {
      while (!stk.isEmpty() && temperatures[stk.peek()] <= temperatures[i]) {
        stk.pop();
      }
      if (!stk.isEmpty()) {
        ans[i] = stk.peek() - i;
      }
      stk.push(i);
    }
    return ans;
  }
}

class Solution {
public:
  vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> ans(n);
    stack<int> stk;
    for (int i = n - 1; ~i; --i) {
      while (!stk.empty() && temperatures[stk.top()] <= temperatures[i]) stk.pop();
      if (!stk.empty()) ans[i] = stk.top() - i;
      stk.push(i);
    }
    return ans;
  }
};

func dailyTemperatures(temperatures []int) []int {
  n := len(temperatures)
  ans := make([]int, n)
  var stk []int
  for i := n - 1; i >= 0; i-- {
    for len(stk) > 0 && temperatures[stk[len(stk)-1]] <= temperatures[i] {
      stk = stk[:len(stk)-1]
    }
    if len(stk) > 0 {
      ans[i] = stk[len(stk)-1] - i
    }
    stk = append(stk, i)
  }
  return ans
}

function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const res = new Array(n).fill(0);
  const stack = [];
  for (let i = 0; i < n; i++) {
    const temperature = temperatures[i];
    while (stack.length !== 0 && temperatures[stack[stack.length - 1]] < temperature) {
      const j = stack.pop();
      res[j] = i - j;
    }
    stack.push(i);
  }
  return res;
}

impl Solution {
  pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
    let n = temperatures.len();
    let mut res = vec![0; n];
    let mut stack = Vec::new();
    for i in 0..n {
      while !stack.is_empty() && temperatures[*stack.last().unwrap()] < temperatures[i] {
        let j = stack.pop().unwrap();
        res[j] = (i - j) as i32;
      }
      stack.push(i);
    }
    res
  }
}