每日温度

怎样从“等几天更高温度;无则 0。”推导出 单调栈 · 每日温度，并证明每次状态变化都不会漏掉答案？

中心结论：单调递减栈存下标,当前更高则弹栈算天数差。

给出一个温度数组，要求输出比当天温度高的在未来的哪一天，输出未来第几天的天数。例如比 73 度高的在未来第 1 天出现，比 75 度高的在未来第 4 天出现。

在本站主例中，等几天更高温度;无则 0。

算法最终需要得到或观察：等待天数数组。

为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“单调候选队列”，明确答案需要观察什么。
2. 2状态只维护 栈、答案数组。
3. 3转移每一步按照 单调递减栈存下标,当前更高则弹栈算天数差。
4. 4收尾读取 等待天数数组。，并复核边界与复杂度。

栈或队列中保存的是仍未找到结论、且保持单调关系的下标。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：栈、答案数组。

这道题根据题意正常处理就可以了。2 层循环。另外一种做法是单调栈，维护一个单调递减的单调栈即可。

单调递减栈存下标,当前更高则弹栈算天数差。

执行过程中持续维护：栈、答案数组。

正确性依赖以下不变量：栈顶是尚未找到更高温度的天。

面试时可以压缩为：单调栈 O(n)。

落到当前题，执行机制可以压缩为：单调递减栈存下标,当前更高则弹栈算天数差。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入等几天更高温度;无则 0。 因为：单调递减栈存下标,当前更高则弹栈算天数差。
2. 2下标 0 入栈等待暂时找不到更高温度。 因为：维持单调性。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4温度 75 > 74,答案[1]=1弹出并记录等待天数。 因为：首次更高温度即最近答案。
5. 5下标 3 入栈等待暂时找不到更高温度。 因为：维持单调性。
6. 6温度 72 > 69,答案[4]=1弹出并记录等待天数。 因为：首次更高温度即最近答案。
7. 7下标 5 入栈等待暂时找不到更高温度。 因为：维持单调性。
8. 8收尾与复杂度等待天数数组。 因为：时间 O(n) · 空间 O(1)。单调递减栈存下标,当前更高则弹栈算天数差。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 普通做法
func dailyTemperatures(T []int) []int {
	res, j := make([]int, len(T)), 0
	for i := 0; i < len(T); i++ {
		for j = i + 1; j < len(T); j++ {
			if T[j] > T[i] {
				res[i] = j - i
				break
			}
		}
	}
	return res
}

// 解法二 单调栈
func dailyTemperatures1(T []int) []int {
	res := make([]int, len(T))
	var toCheck []int
	for i, t := range T {
		for len(toCheck) > 0 && T[toCheck[len(toCheck)-1]] < t {
			idx := toCheck[len(toCheck)-1]
			res[idx] = i - idx
			toCheck = toCheck[:len(toCheck)-1]
		}
		toCheck = append(toCheck, i)
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="daily-temperatures", temps=[73,74,75,71,69,72,76,73]
    //    期望：等待天数数组。
    //
    // 2. 失败 / 未命中
    //    检查：结果单位是天数差不是温度。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC496 NGE；LC503 循环
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意等几天更高温度;无则 0。
2. 2重复为每个位置向两侧重新寻找会重复比较；单调结构及时淘汰以后不可能成为答案的候选。
3. 3优化单调递减栈存下标,当前更高则弹栈算天数差。
4. 4证明栈顶是尚未找到更高温度的天。
5. 5复杂度时间 O(n)，空间 O(1)