739. Daily Temperatures

🟠   🔖  栈 数组 单调栈  🔗 LeetCode

题目

Given an array of integers temperatures represents 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 1:

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

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

Example 2:

Input: temperatures = [30,40,50,60]

Output: [1,1,1,0]

Example 3:

Input: temperatures = [30,60,90]

Output: [1,1,0]

Constraints:

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

题目大意

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

解题思路

• 使用单调递增栈；
• 先遍历一遍 temperatures，并构造单调递增栈，栈中保存元素对应的 index；
• 求出 temperatures 中每个元素右侧下一个更大的元素，然后将其对应的 index 存储到哈希表中；
• 然后再遍历一遍 temperatures，从哈希表中取出对应结果，将差值 value - key 存放到答案数组中；
• 这种解法的时间复杂度是 O(n)。

代码

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  let map = new Map();
  let stack = [];
  for (let i = 0; i < temperatures.length; i++) {
    while (
      stack.length &&
      temperatures[stack[stack.length - 1]] < temperatures[i]
    ) {
      map.set(stack.pop(), i);
    }
    stack.push(i);
  }
  for (let i = 0; i < temperatures.length; i++) {
    temperatures[i] = map.has(i) ? map.get(i) - i : 0;
  }
  return temperatures;
};

相关题目

相关题目

• 496. 下一个更大元素 I
• 901. 股票价格跨度

- [496. 下一个更大元素 I](./0496.md)
- [901. 股票价格跨度](https://leetcode.com/problems/online-stock-span)