每日温度

题目链接

请根据每日气温列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例:

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

思路

解法一：

本题的本质也是求第一个更大的元素。使用单调栈求解,找到更大的数出栈，所以该栈为单调递减栈（从栈底到栈顶）。

由于单调栈满足从栈底到栈顶元素对应的温度递减，因此每次有元素进栈时，会将温度更低的元素全部移除，并更新出栈元素对应的等待天数，这样可以确保等待天数一定是最小的。

结果需要存储下标差值，所以将下标入栈。

当栈不为空和大于栈顶元素时，计算下标差值，并出栈，否则入栈。

#include <iostream>

class Solution
{
public:
    vector<int> dailyTemperatures(vector<int> &temperatures)
    {
        int n = temperatures.size();
        stack<int> stk;
        vector<int> res(n);
        for (int i = 0; i < n; i++)
        {
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) // 找到更大的元素
            {
                int index = stk.top(); 
                res[index] = i - index; //存储下标差值
                stk.pop();
            }
            stk.push(i);
        }
        return res;
    }
};