739. 每日温度

🟠   🔖  栈 数组 单调栈  🔗 力扣 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 来代替。

解题思路

本题的核心在于如何快速找到每一天之后第一个比它大的值。一个直观的方法是双重循环暴力解法，但效率较低（时间复杂度为 O(n^2)）。为了优化，可以使用 单调栈 来实现。

1. 维护一个单调栈，用于存储 [温度值, 索引]，并确保栈中的温度值按从高到低的顺序排列。
2. 初始化一个结果数组 res，长度与 temperatures 相同，初始值为 0。
3. 使用一个 for 循环遍历 temperatures 数组。对于每个温度 temperatures[i]：
   • 检查栈顶元素对应的温度 temperatures[stack[stack.length - 1]] 是否小于当前温度：
     • 如果小于，说明当前温度是栈顶元素对应日期的答案，计算间隔天数并更新结果数组。
     • 重复上述过程直到栈为空或栈顶温度不小于当前温度。
   • 将当前温度和索引 [temperatures[i], i] 压入栈。
4. 遍历结束后，栈中仍未被处理的索引对应的结果值保持为 0（因为没有更暖和的未来日期）。
5. 最后，返回更新后的 res 数组，表示每一天距离下一个更高温度的天数。

复杂度分析

• 时间复杂度： O(n)，其中 n 是 temperatures 数组的长度，需要遍历一次 temperatures 数组，在每个温度的处理过程中，栈的每个元素最多被入栈和出栈各一次，因此，整个算法的时间复杂度为 O(n)。

• 空间复杂度： O(n)，使用了一个栈来存储索引。在最坏情况下（例如，温度是递增的），栈可能会存储所有的索引，空间复杂度为 O(n)。

代码

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
	let res = new Array(temperatures.length).fill(0); // 初始化结果数组
	let stack = []; // 单调递减栈，存储 [温度值, 索引]

	for (let i = 0; i < temperatures.length; i++) {
		// 栈不为空，并且当前温度大于栈顶对应的温度
		while (stack.length && stack[stack.length - 1][0] < temperatures[i]) {
			const [_, idx] = stack.pop(); // 弹出栈顶元素
			res[idx] = i - idx; // 计算天数差并更新结果数组
		}
		// 将当前温度和索引压入栈
		stack.push([temperatures[i], i]);
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
496	下一个更大元素 I	[✓]	栈 数组 哈希表 1+	🟢	🀄️ 🔗
901	股票价格跨度	[✓]	栈 设计 数据流 1+	🟠	🀄️ 🔗