从 O(n²) 到 O(n)：单调栈在算法中的妙用
题目分析
给定一个温度列表 temperatures，要求输出一个同等长度的数组 answer。对于 answer[i] 的定义是：从第 i 天开始，找到下一个比 temperatures[i] 更高的温度所需的天数。如果没有更高的温度，则设为 0。本题实际上可以理解为“寻找下一个更大元素”的变形题。
示例分析
- 输入：
temperatures = [73, 74, 75, 71, 69, 72, 76, 73] - 解释：
- 第1天温度：
73，下一个更高温度是74，出现在第2天，因此answer[0] = 1。 - 第2天温度：
74，下一个更高温度是75，出现在第3天，所以answer[1] = 1。 - 第3天温度：
75，下一个更高温度是76，出现在第6天，因此answer[2] = 4。
- 第1天温度：
通过这个例子可以发现，为了避免重复检查已经确定过结果的温度，我们需要某种方式去“记住”当前还没有找到更高温度的那些温度。这正是单调栈在这里派上用场的原因。
解题方法及分析
暴力法（了解即可）
暴力法思路较为直接：对于每个温度，向后扫描所有天数，直到找到第一个更高的温度。但对于 (n) 长度的数据，它的时间复杂度是 (O(n^2))，在数据量大的情况下会非常耗时。因此我们需要找到更高效的方式——这就是单调栈法。
单调栈法：思路及原理
单调栈是一种特殊的数据结构，通过栈来保证其中的元素具有特定的顺序。我们可以选择递增栈或递减栈来满足不同的需求。本题中，我们使用递减栈，即栈中的温度从栈底到栈顶是递减的。
使用单调栈的原因：
- 当我们遇到一个比栈顶元素更大的温度时，可以确定栈顶元素的下一个更高温度已经找到了。
- 使用单调栈可以避免重复遍历数据，实现一次遍历解决问题。
单调栈解法的具体实现
我们将通过代码实现来讲解每一行的设计思路。
#include <vector>
#include <stack>
using namespace std;
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> answer(n, 0); // 初始化结果数组，默认为0，因为默认情况为“没有更高温度”
stack<int> stack; // 单调递减栈，保存温度数组的索引
// 遍历温度数组
for (int i = 0; i < n; ++i) {
// 栈不为空，并且当前温度大于栈顶索引对应的温度
while (!stack.empty() && temperatures[i] > temperatures[stack.top()]) {
int index = stack.top(); // 获取栈顶索引
stack.pop(); // 弹出栈顶，因为我们已经找到该位置的更高温度
answer[index] = i - index; // 计算天数差并赋值给结果数组
}
stack.push(i); // 将当前天的索引压入栈，等待找到它的更高温度
}
return answer; // 返回结果数组
}
代码细节逐步解析
-
初始化：
vector<int> answer(n, 0);创建结果数组answer，长度为n（即温度数组的长度），并全部初始化为0，表示默认值为“在之后没有更高温度”。
-
遍历温度数组：
- 使用
for循环，从左到右遍历温度列表temperatures。
- 使用
-
处理当前温度与栈顶温度的关系：
while (!stack.empty() && temperatures[i] > temperatures[stack.top()])：如果当前温度temperatures[i]大于栈顶索引对应的温度temperatures[stack.top()]，说明栈顶索引找到了下一个更高温度。
-
更新结果数组：
- 进入
while循环体中，执行以下操作：- 获取栈顶元素
index = stack.top();，这是先前一个温度的索引。 - 弹出栈顶
stack.pop();，表示当前这个索引已经找到了下一个更高温度，不再需要等待。 - 计算该天数差
answer[index] = i - index;，并将结果填入answer数组。
- 获取栈顶元素
- 进入
-
压入当前天的索引：
stack.push(i);：无论是否找到之前的更高温度，当前索引i都需要入栈，表示我们等待找到它的下一个更高温度。
示例分步讲解
我们通过一个模拟的方式，再次演示 temperatures = [73, 74, 75, 71, 69, 72, 76, 73] 的执行过程：
-
初始状态：
answer = [0, 0, 0, 0, 0, 0, 0, 0]，stack = [] -
第1天
i=0, temperatures[0]=73：- 栈为空，将索引
0入栈：stack = [0]
- 栈为空，将索引
-
第2天
i=1, temperatures[1]=74：74 > 73，弹出栈顶索引0，计算answer[0] = 1。- 将索引
1入栈：stack = [1] answer = [1, 0, 0, 0, 0, 0, 0, 0]
-
第3天
i=2, temperatures[2]=75：75 > 74，弹出栈顶索引1，计算answer[1] = 1。- 将索引
2入栈：stack = [2] answer = [1, 1, 0, 0, 0, 0, 0, 0]
-
第4天
i=3, temperatures[3]=71：71 < 75，直接将索引3入栈：stack = [2, 3]
-
第5天
i=4, temperatures[4]=69：69 < 71，直接将索引4入栈：stack = [2, 3, 4]
-
第6天
i=5, temperatures[5]=72：72 > 69，弹出栈顶索引4，计算answer[4] = 1。72 > 71，弹出栈顶索引3，计算answer[3] = 2。- 将索引
5入栈：stack = [2, 5] answer = [1, 1, 0, 2, 1, 0, 0, 0]
-
第7天
i=6, temperatures[6]=76：76 > 72，弹出栈顶索引5，计算answer[5] = 1。76 > 75，弹出栈顶索引2，计算answer[2] = 4。- 将索引
6入栈：stack = [6] answer = [1, 1, 4, 2, 1, 1, 0, 0]
-
第8天
i=7, temperatures[7]=73：73 < 76，直接将索引7入栈：`stack = [6,
7]`
遍历结束，最终 answer 数组为 [1, 1, 4, 2, 1, 1, 0, 0]。
时间复杂度分析
每个索引最多入栈和出栈一次，因此时间复杂度为 (O(n))，这使得本算法在大数据集下也能高效运行。
总结与回顾
通过以上分析，我们掌握了使用单调栈的方法来解决“寻找下一个更高温度”的问题。单调栈不仅适用于温度问题，还广泛应用于“寻找下一个更大/更小元素”一类的题目中，值得深入理解和掌握。在实际工程中，这种方法在数据处理、优化算法性能等方面也有着重要的应用。
原文地址：https://blog.csdn.net/qq_22841387/article/details/143614850
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！