每日温度：从暴力枚举到单调栈线性最优解
一、问题回顾
给定每日气温数组 temperatures，要求输出等长数组 ans：
ans[i]表示第i天之后，首次出现更高气温需要等待的天数；- 若后续无更高气温，值为 0。
问题本质：对数组中每个元素，找到右侧第一个更大元素，并计算下标间距。
二、基础实现：暴力枚举思路与局限
最直观的思路是暴力双重循环：
- 外层遍历每一天
i； - 内层从
i+1向后遍历，找到第一个j满足temperatures[j] > temperatures[i]，记录j-i； - 遍历结束未找到则赋值 0。
// 暴力实现（示意）
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n, 0);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (temperatures[j] > temperatures[i]) {
ans[i] = j - i;
break;
}
}
}
return ans;
}
局限分析
时间复杂度 O(N²)：当数组长度较大（如 10⁴ 及以上）时，循环次数会急剧增加，出现明显性能瓶颈；同时内层循环存在大量重复比较，前序元素的比较结果未被复用，计算效率较低。
三、优化方向：状态复用与单调栈引入
暴力解法的核心问题是：每个元素会被多次比较，没有记录「尚未找到更大值的元素」的状态。
观察遍历过程：
- 我们从左到右遍历，先遍历到的元素，需要等待后遍历的元素来匹配「更大值」；
- 这种「先等待、后匹配」的场景，适合用栈保存未完成匹配的元素状态；
- 为了保证匹配效率，栈需要维持单调递减的特性：栈中元素从栈底到栈顶不递增，确保每次新元素入栈时，能直接找到所有可匹配的栈内元素。
