首页 > 试题广场 >

每日温度

[编程题]每日温度

热度指数：3036 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

根据往后 n 天的天气预报，计算每一天需要等待几天才会出现一次更高的气温，如果往后都没有更高的气温，则用 0 补位。

例如往后三天的气温是 [1,2,3] ，则输出 [1,1,0]

数据范围： $1 \le n \le 10^5 \$ ，每天的温度会满足 $0 \le dailyTemperatures[i] \le 1000 \$

示例1

输入

[1,2,3]

输出

[1,1,0]

示例2

输入

[2,4,5,9,10,0,9]

输出

[1,1,1,1,0,1,0]

示例3

输入

[3,1,4]

输出

[2,1,0]

算法知识视频讲解

查看答案及解析

牛娃牛娃

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 每日温度
     * @param dailyTemperatures int整型vector 
     * @return int整型vector
     */
    vector<int> temperatures(vector<int>& dailyTemperatures) {
        // write code here
        //用单调栈
        int n =dailyTemperatures.size();
        vector<int> res(n);
        stack<int> st;
        for(int i=0;i<n;i++){
            while(!st.empty()&&dailyTemperatures[i]>dailyTemperatures[st.top()]){
                int index =st.top();//栈顶的下标
                res[index] =i-index;
                st.pop();
            }
            st.push(i);//i的温度小于栈顶的温度 或者栈为空 进栈
        }
        return res;
    }
};

/*
栈维护的是下标
栈底到栈顶的下标对应温度列表的温度一次递减栈底最大栈顶最小
遍历温度列表的每个元素下标进栈
1.如果栈为空直接i进栈
2.如果栈不为空比较栈顶元素index对应的温度
如果当前的i温度大于栈顶index的温度，将栈顶移除，并把栈顶对应的等待天数变为i-index
重复上面操作直到i的温度小于栈顶index的温度或者栈为空i进栈

*/

发表于 2022-04-27 16:18:56 回复(0)

这个名字和我无缘

go 的代码是错的没法运行

本地通过了，没法提交测试

func temperatures( temperatures []int ) []int { // write code here  var ret []int = make([]int , len(temperatures)) var a []int   for k , v := range temperatures { if k == 0 { a = append( a , k ) continue  } if v > temperatures[k - 1] { i := len(a) - 1  for i >= 0 && temperatures[a[i]] < v{ ret[ a[i] ] = k - a[i] a = a[ : len(a) - 1 ] i--
         }
      } a = append( a , k )
   } return ret }

发表于 2022-02-25 15:43:44 回复(0)

Java

pein531

单调栈求解，栈中存放索引，遍历数组时构建一个从栈底到栈顶对应数组元素值单调不增的栈。如果遍历到某个温度i时破坏了这个单调性，就开始弹栈，弹出位置下一个比它大的位置都是i，弹栈完成后再把i压栈。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param temperatures int整型一维数组 
     * @return int整型一维数组
     */
    public int[] temperatures (int[] temperatures) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[temperatures.length];
        for(int i = 0; i < temperatures.length; i++){
            if(stack.isEmpty() || temperatures[stack.peek()] > temperatures[i]){
                stack.push(i);
            }else{
                if(temperatures[stack.peek()] == temperatures[i]){
                    stack.push(i);
                }else{
                    while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                        int cur = stack.pop();
                        res[cur] = i - cur;
                    }
                    stack.push(i);
                }
            }
        }
        // 因为res的初始值本来就是0，此步骤可以不要，但为了流程完整性，还是写上
        while(!stack.isEmpty()){
            res[stack.pop()] = 0;
        }
        return res;
    }
}

宏观上看，遍历一遍数组的时间复杂度是O(n)。而弹出栈的元素绝不会再被压回去，所有的元素在整个算法流程中都会来一遍入栈和出栈，因此整体时间复杂度就是O(n)。开辟了一个栈空间来存放数组的索引，因此空间复杂度也为O(n)。

发表于 2021-12-15 12:01:35 回复(0)

Java

合肥吴彦祖

public int[] temperatures (int[] temperatures) {
        // write code here
        int[] ans = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < temperatures.length; i++){
            while(!stack.isEmpty() && temperatures[stack.peek()]  < temperatures[i] ){
                int temp = stack.pop();
                ans[temp] = i-temp;
            }
            stack.push(i);
        }
        return ans;
    }

发表于 2021-12-03 21:05:26 回复(0)

唐氏综合征

这道题比 ONT78 更简单，更容易理解：

1. 使用单调递减栈来存储下标

2. 弹出对于当前元素 i 来说不满足入栈的元素

3. 找到满足刚好使得 i 入栈的元素，

4. 将i 入栈，此时的下标差值就是题目所有

代码里面注释较为清晰，还有画图便于理解：

public int[] temperatures (int[] dailyTemperatures) {
       int len = dailyTemperatures.length;
        int[] res = new int[len];

        // 定义单调栈，单调递减

        /* 下面简单描述了单调stack栈和当前元素i的元素
         *   i    stack
         *        <-
         *       <-
         *  ->  <-
         *     <-
         *    <-
         */

        // 注意点是从未来往过去遍历
        Stack<Integer> stack = new Stack<>();
        for (int i = len - 1; i > -1; i--) {
            while (!stack.isEmpty() && dailyTemperatures[i] >= dailyTemperatures[stack.peek()]) {
                // 如果当前元素比栈顶元素要大的话
                stack.pop();
            }
            // 如果栈不为空，则说明栈顶元素就是比当前元素大的第一个元素, 为空使用默认值
            if (!stack.isEmpty())
                res[i] = stack.peek() - i;
            //当前元素下标入栈
            stack.push(i);
        }
        return res;
    }

发表于 2024-05-13 13:11:13 回复(0)

Java

17c89

import java.util.*;

/**
 * NC208 每日温度
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 每日温度
     * @param dailyTemperatures int整型一维数组 
     * @return int整型一维数组
     */
    public int[] temperatures (int[] dailyTemperatures) {
        int n = dailyTemperatures.length;
        int[] results = new int[n];

        Stack<Integer> stack = new Stack<>();
        // Deque<Integer> stack = new ArrayDeque<>();
        // Deque<Integer> stack = new LinkedList<>();

        for(int i=n-1; i>=0; i--){
            // 单调栈 单调减(从右向左遍历)
            while(!stack.isEmpty() && dailyTemperatures[stack.peek()]<=dailyTemperatures[i]){
                stack.pop();
            }
            // if(stack.isEmpty()){
            //     results[i] = 0;
            // }else{
            //     results[i] = stack.peek()-i;
            // }
            results[i] = stack.isEmpty() ? 0 : stack.peek()-i;
            stack.push(i);
        }

        return results;
    }
}

发表于 2025-02-01 13:15:06 回复(0)

Java

牛客499848474号

不用stack的笨办法，虽然时间空间复杂度都是O(n)

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 每日温度
     * @param dailyTemperatures int整型一维数组 
     * @return int整型一维数组
     */
    public int[] temperatures (int[] dailyTemperatures) {
        // write code here
        int n = dailyTemperatures.length;
        int[] result = new int[n];
        Arrays.fill(result, 0);
        int index = 0;
        for(int i = 0; i < n; i++){
            index = i + 1;
            while(index < n){
                if(dailyTemperatures[index] > dailyTemperatures[i]){
                    result[i] = index - i;
                    break;
                }
                index++;
            }
        }
        return result;
    }
}

发表于 2025-01-05 11:59:26 回复(0)

C++

矜持的微笑

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 每日温度
     * @param dailyTemperatures int整型vector 
     * @return int整型vector
     */
    vector<int> temperatures(vector<int>& T) {
        // write code here
        stack<int> st;  // 递增栈
        vector<int> result(T.size(),0);
        st.push(0);
        for(int i=1;i<T.size();i++){
            while(!st.empty()&&T[i]>T[st.top()]){ //注意栈不能为空
                    result[st.top()]=i-st.top();
                    st.pop();
                }
                st.push(i);
            }
        return result;
    }
};

发表于 2024-01-28 15:35:06 回复(0)

请给PearBao一个offer

华子笔试原题

发表于 2023-09-07 15:11:56 回复(0)

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 每日温度
 * @param dailyTemperatures int整型一维数组 
 * @return int整型一维数组
*/
func temperatures( dailyTemperatures []int ) []int {
    n:=len(dailyTemperatures)
    ans:=make([]int,n)
    stk:=[]int{}
    for i,x:=range dailyTemperatures{
        for len(stk)>0&&dailyTemperatures[stk[len(stk)-1]]<x{
            ans[stk[len(stk)-1]]=i-stk[len(stk)-1]
            stk=stk[:len(stk)-1]
        }
        stk=append(stk,i)
    }
    return ans
}

发表于 2023-03-08 18:51:49 回复(0)

C++

AsherChi

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 每日温度
     * @param dailyTemperatures int整型vector 
     * @return int整型vector
     */
    vector<int> temperatures(vector<int>& dailyTemperatures) {
        // write code here
        stack<int> stc;
        stc.push(0);
        for(int i=dailyTemperatures.size()-2; i>=0; i--)
        {
            if(dailyTemperatures[i] < dailyTemperatures[i+1])
                stc.push(1);
            else
                stc.push(0);
        }
        vector<int> vec;
        while(!stc.empty())
        {
            vec.push_back(stc.top());
            stc.pop();
        }
        // 看错题意了 后面找补了一下 就勉为其难的过了
        for(int i=0; i<vec.size(); i++)
        {
            if(vec[i] == 1)
                continue;
            else
            {
                for(int j = i+1; j<vec.size(); j++)
                {
                    if(dailyTemperatures[j] > dailyTemperatures[i])
                    {
                        vec[i] = j - i;
                        break;
                    }
                }
            }
        }
        return vec;
    }
};

发表于 2022-09-04 11:21:41 回复(0)

C++

牛纸农

vector<int> temperatures(vector<int>& dailyTemperatures) {
// write code here
stack<int> stk;
int n = dailyTemperatures.size();
vector<int> res = vector<int>(n,0);
for(int i = n-1;i>=0;i--){
while(stk.size()&&dailyTemperatures[stk.top()]<=dailyTemperatures[i]){
stk.pop();
}
res[i] = stk.size() == 0?0:stk.top()-i;
stk.push(i);
}
return res;
}

发表于 2022-08-30 13:07:36 回复(0)

牛客508634144号

int* temperatures(int* dailyTemperatures, int dailyTemperaturesLen, int* returnSize )
{
// write code here
int i,j;
int tmp=0;
int* res = (int*)malloc(dailyTemperaturesLen*sizeof(int));
for(i=0; i<dailyTemperaturesLen-1; i++)
{
tmp = dailyTemperatures[i];
for(j=i+1; j<dailyTemperaturesLen; j++)
{
if( tmp<dailyTemperatures[j] )
{
res[i] = j-i;
break;
}
if( 7==j )
res[i] = 0;
}
}

*returnSize = dailyTemperaturesLen;
return res;
}

发表于 2022-07-11 20:32:57 回复(0)

Java

ITwolffy

public int[] temperatures (int[] dailyTemperatures) {
        int n = dailyTemperatures.length;
        int[] res = new int[n];
        //最后一个直接为0
        res[n - 1] = 0;
        //从倒数第2个开始向前遍历
        for (int i = n - 2; i >= 0; i--) {
            //从i的后一位开始比较
            int j = i + 1;
            while (j < n) {
                //如果后一个比当前元素大，则记录距离
                if (dailyTemperatures[i] < dailyTemperatures[j]) {
                    res[i] = j - i;
                    break;
                } else if (res[j] == 0) {//后一位置为0，则说明后面没有比j位置更大温度，则当前遍历的i位置也为0
                    res[i] = 0;
                    break;
                } else {//j位置不为0时,则直接下一个位置：为第一个比j位置大的数
                    j += res[j];
                }
            }
        }
        return res;
    }

发表于 2022-04-14 20:37:21 回复(0)

菜牛柳

编译错误:您提交的代码无法完成编译

main.cpp:28:34: error: called object type 'int *' is not a function or function pointer

int* ret12 = temperatures( temperatures, temperaturesLen, &returnSize);

~~~~~~~~~~~~^

1 error generated.

发表于 2022-02-24 19:51:12 回复(0)

C++

但为卿故

单调栈

class Solution {
public:
vector<int> temperatures(vector<int>& temperatures) {
int len=temperatures.size();
vector<int> m(len,0);
stack<int> s;
for(int i=0;i<len;i++){
if(s.empty()){
s.push(i);
}else{
while(temperatures[i]>temperatures[s.top()]){
m[s.top()]=i-s.top();
s.pop();
if(s.empty()){
break;
}
}
s.push(i);
}
}
return m;
}
};

发表于 2022-02-14 14:24:36 回复(0)

Python 3

牛客38477449号

class Solution:
    def temperatures(self , temperatures: List[int]) -> List[int]:
        # write code here
        stack, res = [], [0] * len(temperatures)
        for i in range(len(temperatures)-1, -1, -1):
            while stack and temperatures[i] >= temperatures[stack[-1]]:
                stack.pop()
            if not stack:
                res[i] = 0
            else:
                res[i] = stack[-1] - i
            stack.append(i)
        return res

发表于 2021-12-24 10:44:53 回复(0)