每日温度

[编程题]每日温度

热度指数：2558 时间限制：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]

算法知识视频讲解

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)

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)