【LeetCode热题100】739. 每日温度（栈）

一.题目要求

给定一个整数数组 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：存每个数的下标，但思路太复杂，让gpt帮我记录一下：

解法2：单调栈，也就是我上面做法的优化

五.代码实现

单调栈

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> stk;
        vector<int> ans(n);
        for(int i = 0; i < n; i++)
        {
            if(stk.empty())
            {
                stk.push(i);
            }
            else
            {
                while(!stk.empty() && temperatures[i] > temperatures[stk.top()])
                {
                    ans[stk.top()] = i - stk.top();
                    stk.pop();
                }
                stk.push(i);
            }
        }
        return ans;
    }
};

自己的解法，仅记录

class Solution {
public:

    static int cmp(pair<int,int> a, pair<int,int> b)
    {
        return a.first < b.first;
    }

    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk;
        stack<pair<int, int>> count;
        vector<pair<int, int>> ans;
        for(int i = 0; i < temperatures.size(); i++) 
        {
            if(stk.empty()) 
            {
                stk.push(temperatures[i]);
                count.push({i, 0});
            }
            else 
            {
                while(!stk.empty() && temperatures[i] > stk.top()) 
                {
                    
                    ans.push_back({count.top().first, count.top().second + 1});
                    int tmp = count.top().second;
                    count.pop();
                    if(!count.empty())
                        count.top().second =count.top().second + tmp + 1;
                    stk.pop();
                }
                stk.push(temperatures[i]);
                count.push({i, 0});
            }
        }
        while(!count.empty()) {
             ans.push_back({count.top().first, 0});
             count.pop();
        }
        sort(ans.begin(), ans.end(), cmp);

        vector<int> aans; for(auto v : ans) aans.push_back(v.second);

       return aans;
    }
};

六.题目总结

判别是否需要使用单调栈，如果需要找到左边或者右边第一个比当前位置的数大或者小，则可以考虑使用单调栈。