LeetCode739每日温度
LeetCode 上的 739每日温度
这是 LeetCode 上的 739. 每日温度，标准解法是 单调递减栈。下面我换一种**“找下一个更大元素”**的生活化方式，帮你把代码和图解对应上，保证你理解后永远忘不掉。
第一层：暴力思路（先理解题目在干嘛）
题目要我们找：每个元素右边第一个比它大的元素，距离它有多远。
- 输入：
[73, 74, 75, 71, 69, 72, 76, 73] - 输出：
[1, 1, 4, 2, 1, 1, 0, 0]
手工验证一下：
73右边第一个比它大的是74，下标差1✅75右边第一个比它大的是76，下标差4（75在索引2，76在索引6，6-2=4）✅76右边没有比它更大的，0✅
如果用两层循环暴力解，时间复杂度 O(n²)，数据量大时（10⁵）会超时。所以需要 单调栈 优化到 O(n)。
第二层：单调栈核心思想（生活类比）
想象你在排队，每个人手里举着一个牌子，上面写着今天的温度。
规则：新来的人如果比栈顶的人温度高，那栈顶的人就找到了答案（新来的人就是他的“下一个更高温度”），于是栈顶的人出栈（记录答案），新来的人继续和新的栈顶比较。如果新来的人不比栈顶高，那就直接入栈（等待后面更热的人）。
关键：栈里存的是数组下标（索引），而不是温度值。因为计算天数差需要索引。
第三层：完整图解（用示例跑一遍）
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]result 初始化为 [0, 0, 0, 0, 0, 0, 0, 0]
第 0 步：栈为空，0 入栈 → 栈 [0]
第 1 步（温度 74）：
- 栈顶是
0（温度 73），74 > 73 → 找到了答案！result[0] = 1 - 0 = 1，0出栈
- 栈空了，
1入栈 → 栈[1]
第 2 步（温度 75）：
- 栈顶是
1（温度 74），75 > 74 → 找到了答案！result[1] = 2 - 1 = 1，1出栈
- 栈空了，
2入栈 → 栈[2]
第 3 步（温度 71）：
- 栈顶是
2（温度 75），71 > 75？否 → 不入栈，3入栈 → 栈[2, 3]
第 4 步（温度 69）：
- 栈顶是
3（温度 71），69 > 71？否 →4入栈 → 栈[2, 3, 4]
第 5 步（温度 72）：
- 栈顶是
4（温度 69），72 > 69 → 找到了！result[4] = 5 - 4 = 1，4出栈
- 栈顶是
3（温度 71），72 > 71 → 找到了！result[3] = 5 - 3 = 2，3出栈
- 栈顶是
2（温度 75），72 > 75？否 → 停止比较 5入栈 → 栈[2, 5]
第 6 步（温度 76）：
- 栈顶是
5（温度 72），76 > 72 → 找到了！result[5] = 6 - 5 = 1，5出栈
- 栈顶是
2（温度 75），76 > 75 → 找到了！result[2] = 6 - 2 = 4，2出栈
- 栈空了，
6入栈 → 栈[6]
第 7 步（温度 73）：
- 栈顶是
6（温度 76），73 > 76？否 →7入栈 → 栈[6, 7]
遍历结束，栈里剩下的 [6, 7] 对应温度 [76, 73]，右边没有更大的了，保持 0。
最终结果：[1, 1, 4, 2, 1, 1, 0, 0] ✅
第四层：完整代码（你把逻辑和代码一一对应上）
function dailyTemperatures(temperatures) {
const n = temperatures.length;
const result = new Array(n).fill(0);
const stack = []; // 存索引
for (let i = 0; i < n; i++) {
// 只要当前温度 > 栈顶索引对应的温度，就说明找到了答案
while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
const topIndex = stack.pop();
result[topIndex] = i - topIndex; // 计算天数差
}
// 当前索引入栈
stack.push(i);
}
return result;
}第五层：面试官追问与你的回答
追问1：“为什么栈里存索引而不存值？”
“因为我们要计算天数差（索引差），存值无法计算距离。取值时通过
temperatures[stack[stack.length - 1]]拿到。”
追问2：“为什么结果是 O(n)？”
“每个元素最多入栈一次、出栈一次，所以总操作次数是 2n，复杂度 O(n)。”
追问3：“如果温度相等怎么办？”
“题目要求更高温度，相等不算。用
>而不是>=，所以相等元素会直接入栈，不会错误计算。”
第六层：面试话术（怎么讲给面试官听）
“这道题我选择单调递减栈。具体做法是：遍历数组，维护一个栈，栈里存的是还没找到下一个更高温度的索引。
每次遇到新温度，我就检查栈顶索引对应的温度是否比当前温度低。如果低，说明栈顶元素的下一个更高温度就是当前这个温度，我立刻计算天数差并记录，然后把栈顶弹出。继续比较新的栈顶。直到栈空或栈顶温度不比当前温度低，再把当前索引入栈。
这样每个元素只入栈一次、出栈一次，时间复杂度 O(n)，空间复杂度 O(n)。”