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

从 O(n²) 到 O(n)：单调栈在算法中的妙用

article 2024/11/13 22:33:50

题目分析

给定一个温度列表 temperatures，要求输出一个同等长度的数组 answer。对于 answer[i] 的定义是：从第 i 天开始，找到下一个比 temperatures[i] 更高的温度所需的天数。如果没有更高的温度，则设为 0。本题实际上可以理解为“寻找下一个更大元素”的变形题。

题目链接：739. 每日温度 - 力扣（LeetCode）

示例分析

输入：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。

通过这个例子可以发现，为了避免重复检查已经确定过结果的温度，我们需要某种方式去“记住”当前还没有找到更高温度的那些温度。这正是单调栈在这里派上用场的原因。

解题方法及分析

暴力法（了解即可）

暴力法思路较为直接：对于每个温度，向后扫描所有天数，直到找到第一个更高的温度。但对于 (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,