《灵珠觉醒：从零到算法金仙的C++修炼》卷八·鸿蒙初判（77）诛仙阵封单调栈 - 每日温度（单调栈应用）

在这篇文章中，我们跟随小哪吒学习了如何使用单调栈解决每日温度问题。通过暴力解法的尝试，哪吒意识到双重循环虽然直观，但效率低下。在太乙真人的指引下，他领悟了单调栈的精髓，通过维护一个递减的温度序列，高效地找到每个温度的下一个更高温度，大幅减少了时间复杂度。我们还详细介绍了C++中向量和栈的基本操作。通过这次修炼，哪吒不仅提升了算法能力，还对单调栈的应用有了更深刻的理解。

轻口味

1538人浏览 · 2025-03-19 15:00:00

轻口味 · 2025-03-19 15:00:00 发布

《灵珠觉醒：从零到算法金仙的C++修炼》卷八·鸿蒙初判（77）诛仙阵封单调栈 - 每日温度（单调栈应用）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的诛仙阵，阵中弥漫着温度的波动，代表着单调栈的奥秘。阵的入口处有一块巨大的石碑，上面刻着一行文字：“欲封此阵，需以诛仙之力，用单调栈，每日温度显真身。”

哪吒定睛一看，石碑上还有一行小字：“当温度数组为[73, 74, 75, 71, 69, 72, 76]时，输出每个温度的下一个更高温度的索引。”哪吒心中一动，他知道这是一道关于单调栈应用的难题，需要通过单调栈来高效解决。

暴力解法：诛仙阵的初次尝试

哪吒心想：“要找到每个温度的下一个更高温度，我可以尝试对每个温度，向后遍历直到找到更高的温度。”他催动诛仙阵之力，通过双重循环，逐个比较温度值，试图得到结果。

#include <iostream>
#include <vector>

using namespace std;

vector<int> dailyTemperatures(vector<int>& temperatures) {
    vector<int> result(temperatures.size(), 0);
    for (int i = 0; i < temperatures.size(); ++i) {
        for (int j = i + 1; j < temperatures.size(); ++j) {
            if (temperatures[j] > temperatures[i]) {
                result[i] = j - i;
                break;
            }
        }
    }
    return result;
}

int main() {
    vector<int> temperatures = {73, 74, 75, 71, 69, 72, 76};
    vector<int> result = dailyTemperatures(temperatures);
    cout << "每个温度的下一个更高温度的索引为：";
    for (int res : result) {
        cout << res << " ";
    }
    cout << endl;
    return 0;
}

哪吒成功地得到了结果，但诛仙阵的光芒却黯淡了下来。他意识到，这种方法时间复杂度高达O(n^2)，在温度数据较大时，灵力消耗巨大，效率低下。

C++语法点

在C++中，单调栈的实现涉及到向量和栈的操作。以下是一些重要特性：

向量操作：
- 使用vector类型存储温度数据和结果。
- 使用push_back和pop_back方法修改向量。
栈操作：
- 使用stack容器适配器实现栈功能。
- 使用push、pop和top方法操作栈。

高阶优化：单调栈的智慧

哪吒元神中突然浮现金色铭文——「诛仙阵封单调栈，每日温度显真身」。他领悟到，可以通过单调栈的特性，维护一个递减的温度序列，从而高效地找到每个温度的下一个更高温度。

哪吒决定使用单调栈，从后往前遍历温度数组，将温度和索引压入栈中，保持栈内温度的递减顺序。通过这种方式，他成功地将时间复杂度降低到O(n)，大幅减少了灵力消耗。

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<int> dailyTemperatures(vector<int>& temperatures) {
    vector<int> result(temperatures.size(), 0);
    stack<pair<int, int>> stk; // 存储温度和索引

    for (int i = temperatures.size() - 1; i >= 0; --i) {
        while (!stk.empty() && stk.top().first <= temperatures[i]) {
            stk.pop();
        }
        if (!stk.empty()) {
            result[i] = stk.top().second - i;
        }
        stk.push({temperatures[i], i});
    }
    return result;
}

int main() {
    vector<int> temperatures = {73, 74, 75, 71, 69, 72, 76};
    vector<int> result = dailyTemperatures(temperatures);
    cout << "每个温度的下一个更高温度的索引为：";
    for (int res : result) {
        cout << res << " ";
    }
    cout << endl;
    return 0;
}