LeetCode 热题 100_每日温度（72_739_中等_C++）(栈)（暴力破解；栈（从左到右）；栈（从右到左））

题目描述：

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

输入输出样例：

示例 1：
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2：
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3：
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：
1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100

题解：

解题思路：

思路一（暴力破解法(双重循环)）：

1、我们需要遍历每一天的温度，并找到之后的某一天，找到第一个比当前温度大的温度。每次找到一个比当前温度大的温度时，计算两者的天数差，并保存这个结果。如果遍历完整个数组没有找到比当前温度大的温度，那么该位置的 ans[i] 就是 0。

2、具体思路如下：
① 我们用一个 ans 数组来保存每一天的答案，初始化为 0。
② 外层循环遍历每一天的温度。
③ 内层循环从当前天的后一天开始，向后查找温度较大的那一天。如果找到，则记录下两天的天数差。
④ 如果没有找到比当前温度更高的温度，ans[i] 保持为 0。

3、复杂度分析：
① 时间复杂度：O(n²)，使用了双重循环。
② 空间复杂度：O(1)，除存储的答案数组外，使用常数个空间。

思路二（栈：从左到右）：

1、解题思路

• 我们从左往右遍历温度数组 temperatures，并通过栈保存尚未找到更高温度的元素的下标。
• 每次遇到一个比栈顶元素大的温度时，就意味着找到了栈顶下标对应的温度之后的第一个更高温度。此时就可以计算出天数差并将栈顶元素出栈。
• 如果当前温度比栈顶元素的温度小或相等，则将当前下标压入栈中。

2、具体思路如下：
① 首先将答案数组赋值为0，从左向右遍历元素。
② 当前栈非空 且 当前元素大于栈顶元素，则栈顶元素出栈，并计算出天数差（直至此元素不大于栈顶元素，或栈为空）。将当前元素进栈。
③ 其余两种情况：栈空则直接入栈，当前元素小于等于栈顶元素直接入栈。

3、复杂度分析
① 时间复杂度：O(n)，其中 n 是数组中的元素数量。因只遍历一遍数组。
② 空间复杂度：O(n)，最坏的情况下所有的元素都需进栈。

思路三（栈：从右到左）：

1、解题思路

• 我们从右往左遍历温度数组 temperatures，并通过栈保存还未遍历的左侧结点可能的更高温度。
• 当前栈非空 且 当前元素大于等于栈顶元素，则栈顶元素出栈（直至此元素小于栈顶元素，或栈为空）。将当前元素进栈。
• 其余两种情况：栈空则直接入栈。当前元素小于栈顶元素计算天数差并将元素入栈。

2、具体思路如下：
① 首先将答案数组赋值为0，从右向左遍历元素。
② 当前栈非空 且 当前元素大于等于栈顶元素，则栈顶元素出栈（直至此元素小于栈顶元素，或栈为空）。将当前元素进栈。
③ 其余两种情况：栈空则直接入栈。当前元素小于栈顶元素直接入栈并计算天数差。

3、复杂度分析
① 时间复杂度：O(n)，其中 n 是数组中的元素数量。因只遍历一遍数组。
② 空间复杂度：O(n)，最坏的情况下所有的元素都需进栈（方法三较方法二而言，栈中没有存储相同的元素）。

代码实现

代码实现（思路一（暴力破解法(双重循环)））：

class Solution1 {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        // 初始化一个大小为 temperatures.size() 的结果数组 ans，默认值为 0
        vector<int> ans(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]) {
                    // 记录两天的天数差
                    ans[i] = j - i;
                    // 跳出内层循环，因为已经找到了第一个比当前温度大的温度
                    break;
                }
            }
        }

        // 返回最终的结果数组
        return ans;
    }
};

代码实现（思路二（栈：从左到右））：

class Solution2 {
public:
    // dailyTemperatures函数接受一个整数数组temperatures，返回一个与该数组长度相同的结果数组。
    // 结果数组的每个元素表示从当前天开始，经过多少天温度才会比当前温度高。
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk;  // 栈，用来存储温度数组的索引。
        vector<int> ans(temperatures.size(), 0);  // 结果数组，初始值为0，大小与输入数组相同。

        // 遍历温度数组
        for (int i = 0; i < temperatures.size(); i++) {
            // 如果栈不为空且当前温度大于栈顶所对应的温度
            // 说明找到了栈顶温度的下一个较高温度，记录间隔天数并弹出栈顶元素。
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                ans[stk.top()] = i - stk.top();  // 计算天数差，更新结果数组。
                stk.pop();  // 弹出栈顶元素。
            }
            stk.push(i);  // 当前天的索引入栈，待后续天数比较。
        }
        
        return ans;  // 返回结果数组，包含每一天的等待天数。
    }
};

代码实现（思路三（栈：从右到左））：

class Solution3 {
public:
    // dailyTemperatures函数接受一个整数数组temperatures，返回一个与该数组长度相同的结果数组。
    // 结果数组的每个元素表示从当前天开始，经过多少天温度才会比当前温度高。
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk;  // 栈，用来存储温度数组的索引。
        vector<int> ans(temperatures.size(), 0);  // 结果数组，初始值为0，大小与输入数组相同。

        // 从后往前遍历温度数组
        for (int i = temperatures.size() - 1; i >= 0; i--) {
            // 如果栈不为空且当前温度大于等于栈顶所对应的温度
            // 说明当前天的温度不能找到比它更高的温度，因此需要弹出栈顶元素。
            while (!stk.empty() && temperatures[i] >= temperatures[stk.top()]) {
                stk.pop();  // 弹出栈顶元素，因为当前温度比栈顶的温度要大或者相等，找不到更高的温度。
            }

            // 如果栈不为空，说明栈顶索引对应的温度大于当前温度
            // 那么栈顶索引对应的温度就是当前温度的下一个较高温度。
            if (!stk.empty()) {
                ans[i] = stk.top() - i;  // 计算天数差，更新结果数组。
            }

            // 将当前天的索引入栈，等待后续天数的比较。
            stk.push(i);
        }

        return ans;  // 返回结果数组，包含每一天的等待天数。
    }
};

以思路二为例进行调试

#include<iostream>
#include <vector>
#include<stack>
using namespace std;

class Solution2 {
public:
    // dailyTemperatures函数接受一个整数数组temperatures，返回一个与该数组长度相同的结果数组。
    // 结果数组的每个元素表示从当前天开始，经过多少天温度才会比当前温度高。
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk;  // 栈，用来存储温度数组的索引。
        vector<int> ans(temperatures.size(), 0);  // 结果数组，初始值为0，大小与输入数组相同。

        // 遍历温度数组
        for (int i = 0; i < temperatures.size(); i++) {
            // 如果栈不为空且当前温度大于栈顶所对应的温度
            // 说明找到了栈顶温度的下一个较高温度，记录间隔天数并弹出栈顶元素。
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                ans[stk.top()] = i - stk.top();  // 计算天数差，更新结果数组。
                stk.pop();  // 弹出栈顶元素。
            }
            stk.push(i);  // 当前天的索引入栈，待后续天数比较。
        }
        
        return ans;  // 返回结果数组，包含每一天的等待天数。
    }
};
int main(int argc, char const *argv[])
{
    vector<int> temperatures={73,74,75,71,69,72,76,73};

    Solution2 s2;
    vector<int> ans=s2.dailyTemperatures(temperatures);
    for (auto &i : ans){
        cout<<i<<" ";
    }
    
    return 0;
}

LeetCode 热题 100_每日温度（72_739)原题链接
欢迎大家和我沟通交流(✿◠‿◠)