739.每日温度

链接：739.每日温度
难度：Medium
标签：栈、数组、单调栈
简介：根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

题解 1 - typescript

• 编辑时间：2020-06-11
• 执行用时：1732ms
• 内存消耗：45.5MB
• 编程语言：typescript
• 解法介绍：倒序遍历，相比起正序遍历的每次都遍历到重复值节约时间。

function dailyTemperatures(T: number[]): number[] {
  const len = T.length;
  if (len === 0) return [];
  let ans: number[] = [];
  for (let i = len - 1; i >= 0; i--) {
    if (i === len - 1) {
      ans.unshift(0);
      continue;
    }
    ans.unshift(find(T[i], i + 1));
  }
  return ans;
  function find(num: number, index: number): number {
    for (let i = index; i < len; i++) if (T[i] > num) return i - index + 1;
    return 0;
  }
}

题解 2 - typescript

• 编辑时间：2020-06-11
• 执行用时：196ms
• 内存消耗：50.3MB
• 编程语言：typescript
• 解法介绍：维护单调栈，栈顶元素小于当前元素即赋值。

function dailyTemperatures(T: number[]): number[] {
  const stack: number[] = [];
  const ans: number[] = [];
  for (let i = 0, len = T.length; i < len; i++) {
    while (stack.length !== 0 && T[stack.slice(-1)[0]] < T[i]) {
      const index = stack.pop() as number;
      ans[index] = i - index;
    }
    stack.push(i);
  }
  while (stack.length !== 0) ans[stack.pop() as number] = 0;
  return ans;
}

题解 3 - typescript

• 编辑时间：2021-07-19
• 执行用时：240ms
• 内存消耗：60.6MB
• 编程语言：typescript
• 解法介绍：单调递增栈。

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