[LeetCode 739] Daily Temperatures（每日温度）（栈）

比眉伴天荒 2023-07-04 08:55 37阅读 0赞

**目录**

题目描述

解题思路

代码实现

题目地址：https://leetcode-cn.com/problems/daily-temperatures

--------------------

## 题目描述 ##

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = \[73, 74, 75, 71, 69, 72, 76, 73\], your output should be \[1, 1, 4, 2, 1, 1, 0, 0\].

Note: The length of temperatures will be in the range \[1, 30000\]. Each temperature will be an integer in the range \[30, 100\].

根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = \[73, 74, 75, 71, 69, 72, 76, 73\]，你的输出应该是 \[1, 1, 4, 2, 1, 1, 0, 0\]。

提示：气温 列表长度的范围是 \[1, 30000\]。每个气温的值的均为华氏度，都是在 \[30, 100\] 范围内的整数。

## 解题思路 ##

最简单的办法就是O(n^2)复杂度的遍历……显然太慢了 因为重复遍历了很多很多很多次

所以想到利用栈来记录一个非递减的序列。这里引用官方的题解⬇️

我们需要找到比当前 T\[i\] 温度更高的位置，那么必须要记录哪些信息？  
我们试着找到 T\[0\] 过后温度升高的位置。如果知道 T\[10\]=50，则 T\[20\]=50 是无效信息，因为 T\[i\] 在 T\[20\] 以前已经到达了 50。如果 t\[20\]=100 将是有用的信息，因为如果 t\[0\]=80，那么 T\[20\] 将有可能是它的下一个温度升高的位置，而 T\[10\] 则不可能是。  
**因此，我们需要记住一个索引的列表，索引代表的温度严格递增。我们可以利用栈来实现这样的效果。**

算法：

我们用栈记录索引，满足 T\[stack\[-1\]\] < T\[stack\[-2\]\] < ...，其中 stack\[-1\] 是栈的顶部，stack\[-2\] 是从顶部开始的第二个元素，依此类推；我们将在处理每个 T\[i\] 时保持 stack\[-1\] > stack\[-2\] > ...。  
我们**通过当前温度和栈顶索引所代表的温度比较来找到温度升高的位置**。  
举个例子：我们**反向遍历**处理 t=\[73，74，75，71，69，72，76，73\] ，通过看栈元素的变化来理解是如何工作的。为了清楚 stack 只包含索引 i，但是将把 T\[i\] 的值写在旁边的括号中，例如 0 (73)。  
当 i = 7，stack = \[7 (73)\]。ans\[i\] = 0。  
当 i = 6，stack = \[6 (76)\]。ans\[i\] = 0。  
当 i = 5，stack = \[5 (72), 6 (76)\]。ans\[i\] = 1。  
当 i = 4，stack = \[4 (69), 5 (72), 6 (76)\]。ans\[i\] = 1。  
当 i = 3，stack = \[3 (71), 5 (72), 6 (76)\]。ans\[i\] = 2。  
当 i = 2，stack = \[2 (75), 6 (76)\]。ans\[i\] = 4。  
当 i = 1，stack = \[1 (74), 2 (75), 6 (76)\]。ans\[i\] = 1。  
当 i = 0，stack = \[0 (73), 1 (74), 2 (75), 6 (76)\]。ans\[i\] = 1。

作者：LeetCode  
链接：https://leetcode-cn.com/problems/daily-temperatures/solution/mei-ri-wen-du-by-leetcode/

## 代码实现(C++) ##

正序遍历（比反向慢）：

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

反向遍历：

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