一.题目要求

给定一个整数数组 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;}
};

六.题目总结

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