力扣739.每日温度

ccf19881030

发布于 2023-04-06 11:12:16

1780

发布于 2023-04-06 11:12:16

文章被收录于专栏：ccf19881030的博客ccf19881030的博客

力扣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^5
30 <= temperatures[i] <= 100

暴力解法：两层遍历 O(n^2)时间复杂度超时

本题很容易想到的一种解法是，使用两层for循环，计算每个位置后面第一个比自己大的元素位置。代码如下：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> results(temperatures.size(), 0);
        for (int i = 0; i < temperatures.size(); i++) {
            for (int j = i + 1; j < temperatures.size(); j++) {
                if (temperatures[j] > temperatures[i]) {
                    results[i] = j - i;
                    break;
                }
            }
        }
        return results;
    }
};

提交之后超时了，如下图所示：

单调栈

解题思路

使用单调栈，栈中存放的是数组的下标，从栈顶到栈尾是单调递增的。 1、初始化将结果数组results大小初始化为temperatures的大小，默认初始值为-1 2、借助一个栈stack s;首先往栈中放入下标0 3、遍历温度数组temperatures，从1~temperatures.size()-1， 1）、如果栈非空，并且当前温度（下标为i）大于栈顶下标s.top对应的温度，则进行如下处理： A、计算results[s.top()]的值，即为：i - s.top()，用当前元素下标减去栈顶元素 B、将栈顶元素弹出执行步骤1）知道不满足上述条件为止。将下标i放入栈中 2）、将下标i放入栈中

C++实现代码如下：

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2023-04-05，如有侵权请联系 cloudcommunity@tencent.com 删除

c++