题目链接：leetcode 739

1.题目

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

2.示例

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

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

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

3.数据范围

1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100

3. 分析

这道题目卡到了第二天才A，确实是对栈不太熟悉，没有想到。最开始的思路是搞双指针，但是这个寻找当前最近的温度也不满足双指针的要求。接下来，我又剑走偏锋，我看到30 <= temperatures[i] <= 100，就想着能不能把这个数字离散化，分别记录30-100的每个数的位置列表，再调一个二分找到位置，但是这样的时间复杂度是nlogn，还是T了。最后想到可以利用栈去解决这个问题，具体地讲，我们需要维护的是一个递减的栈，我们循环0-temperatures.size()-1的每一个位置的数，我们设当前的数为cur,那么当cur大于栈顶的时候，说明cur就是栈顶元素能遇到的最近的比他大的数字了，我们就把栈顶元素对应的答案更正为cur-栈顶，并pop一下，这样我们就能找到所有元素对应的答案了。（同时考虑特殊情况，初始化所有位置对应的答案均为0）

4.代码

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