当前位置：首页 > news >正文

算法题-25

news 2026/3/26 20:15:49

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

拿到这道题最容易想到的对每一天往后找：
for i:
for j = i+1 → n:
找第一个 > temperatures[i]
时间复杂度O(n²)，数据量过大就会直接爆炸

但是核心问题是我们什么时候才能知道某一天的答案呢，只有后面的数才能决定前面的答案，这意味需要回头更新，所以需要栈。

我们拿示例1作为例子

说明：stack：存的是「下标(温度)」，操作：当前发生了什么，res：当前答案状态

i	当前温度	操作说明	stack（下标→温度）	res
-	-	初始化	[]	[0,0,0,0,0,0,0,0]
0	73	栈空，入栈	[0→73]	[0,0,0,0,0,0,0,0]
1	74	74>73，弹0，res[0]=1	[]	[1,0,0,0,0,0,0,0]
1	74	入栈1	[1→74]	[1,0,0,0,0,0,0,0]
2	75	75>74，弹1，res[1]=1	[]	[1,1,0,0,0,0,0,0]
2	75	入栈2	[2→75]	[1,1,0,0,0,0,0,0]
3	71	71<75，入栈	[2→75,3→71]	[1,1,0,0,0,0,0,0]
4	69	69<71，入栈	[2→75,3→71,4→69]	[1,1,0,0,0,0,0,0]
5	72	72>69，弹4，res[4]=1	[2→75,3→71]	[1,1,0,0,1,0,0,0]
5	72	72>71，弹3，res[3]=2	[2→75]	[1,1,0,2,1,0,0,0]
5	72	72<75，停止弹栈并入栈	[2→75,5→72]	[1,1,0,2,1,0,0,0]
6	76	76>72，弹5，res[5]=1	[2→75]	[1,1,0,2,1,1,0,0]
6	76	76>75，弹2，res[2]=4	[]	[1,1,4,2,1,1,0,0]
6	76	入栈6	[6→76]	[1,1,4,2,1,1,0,0]
7	73	73<76，入栈	[6→76,7→73]	[1,1,4,2,1,1,0,0]
结束	-	栈剩元素无更高温度	[6,7]	[1,1,4,2,1,1,0,0]

观察表格会发现：栈里永远保持温度递减75，71，69，当更大温度出现：72 或 76，就会：连续弹栈 + 批量结算

var dailyTemperatures = function(temperatures) { const n = temperatures.length const res = new Array(n).fill(0) const stack = [] // 存下标 for(let i = 0; i < n; i++){ // 当前温度更高 → 结算之前的 while( stack.length && temperatures[i] > temperatures[stack[stack.length - 1]] ){ const prevIndex = stack.pop() res[prevIndex] = i - prevIndex } stack.push(i) } return res };

核心思想就是使用单调递减栈保存尚未找到更高温度的下标，当遇到更高温度时，依次弹出并计算等待天数。

查看全文

http://www.jsqmd.com/news/421696/