每日温度( LeetCode 739 )

一、题目描述

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

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

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

二、题目解析

这道题目最 “难” 的一个点是题目的理解。

给定列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],为啥输出就是 [1, 1, 4, 2, 1, 1, 0, 0]

下面来一个个进行解释。

对于输入 73,它需要 经过一天 才能等到温度的升高,也就是在第二天的时候,温度升高到 74 ,所以对应的结果是 1。

对于输入 74,它需要 经过一天 才能等到温度的升高,也就是在第三天的时候,温度升高到 75 ,所以对应的结果是 1。

对于输入 75,它经过 1 天后发现温度是 71,没有超过它,继续等,一直 等了四天,在第七天才等到温度的升高,温度升高到 76 ,所以对应的结果是 4 。

对于输入 71,它经过 1 天后发现温度是 69,没有超过它,继续等,一直 等了两天,在第六天才等到温度的升高,温度升高到 72 ,所以对应的结果是 2 。

对于输入 69,它 经过一天 后发现温度是 72,已经超过它,所以对应的结果是 1 。

对于输入 72,它 经过一天 后发现温度是 76,已经超过它,所以对应的结果是 1 。

对于输入 76,后续 没有温度 可以超过它,所以对应的结果是 0 。

对于输入 73,后续 没有温度 可以超过它,所以对应的结果是 0 。

也就是说,这道题目就是给你一个值,让你找到右边第一个比它大的数,它们两则的下标差就是输出结果

好了,理解了题意我们来思考如何求解:借助单独递增栈来处理。

具体操作如下:

遍历整个数组,如果栈不空,且当前数字大于栈顶元素,那么如果直接入栈的话就不是 递增栈 ,所以需要取出栈顶元素,由于当前数字大于栈顶元素的数字,而且一定是第一个大于栈顶元素的数,直接求出下标差就是二者的距离。

继续看新的栈顶元素,直到当前数字小于等于栈顶元素停止,再将数字入栈,这样就可以一直保持递增栈,且每个数字和第一个大于它的数的距离也可以算出来。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 每日温度( LeetCode 739 ):https://leetcode-cn.com/problems/daily-temperatures
class Solution {
    /**
     * 维护一个单调递增栈,栈内元素从栈底到栈顶依次减小
     * 入栈的元素要和当前栈内栈首元素进行比较
     * 如果大于栈首元素,说明温度比之前更高,那么它们的下标差就是栈首元素等了多少天等到的更高温度的结果
     * 如果小于栈首元素,说明温度比之前更低,说明还没有等到更高的温度,直接放入到栈中
     */
    public static int[] dailyTemperatures(int[] temperatures) {

        // 构建一个栈,用来存放每日温度的下标
        Stack<Integer> stack = new Stack<>();

        // 构建一个数组,用来保存输出结果
        int[] res = new int[temperatures.length];

        // 从头开始遍历每天的温度
        for (int i = 0; i < temperatures.length; i++) {

            // 拿到当天的温度,需要和栈首元素进行比较
            // 如果此时栈不为空并且当天的温度大于栈首元素
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {

                // 首先获取栈首元素的值,并将元素从栈中移除
                int preIndex = stack.pop();

                // 它们的下标差就是栈首元素等了多少天等到的更高温度的结果,保存到输出数组 res 中
                res[preIndex] = i - preIndex;
            }

            // 再把当天的温度的下标值存放到栈中
            stack.push(i);
        }
        // 最后输出 res 数组即可
        return res;
    }

}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 每日温度( LeetCode 739 ):https://leetcode-cn.com/problems/daily-temperatures
/**
* 维护一个单调递增栈,栈内元素从栈底到栈顶依次减小
* 入栈的元素要和当前栈内栈首元素进行比较
* 如果大于栈首元素,说明温度比之前更高,那么它们的下标差就是栈首元素等了多少天等到的更高温度的结果
* 如果小于栈首元素,说明温度比之前更低,说明还没有等到更高的温度,直接放入到栈中
*/
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        // 构建一个栈,用来存放每日温度的下标
        stack<int> stk;

        // 构建一个数组,用来保存输出结果
        vector<int> res(T.size());

        // 从头开始遍历每天的温度
        for (int i = 0; i < T.size(); i++) {

            // 拿到当天的温度,需要和栈首元素进行比较
            // 如果此时栈不为空并且当天的温度大于栈首元素
            while (!stk.empty() && T[i] > T[stk.top()]) {

                // 首先获取栈首元素的值,并将元素从栈中移除
                int preIndex = stk.top();

                stk.pop();

                // 它们的下标差就是栈首元素等了多少天等到的更高温度的结果,保存到输出数组 res 中
                res[preIndex] = i - preIndex;
            }

            // 再把当天的温度的下标值存放到栈中
            stk.push(i);
        }
        // 最后输出 res 数组即可
        return res;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 每日温度( LeetCode 739 ):https://leetcode-cn.com/problems/daily-temperatures
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:

        # 构建一个栈,用来存放每日温度的下标
        stack = []

        # 获取数组长度
        length = len(temperatures)

        # 构建一个数组,用来保存输出结果
        res = [0] * length

        # 从头开始遍历每天的温度
        for i in range(length):
            #  拿到当天的温度,不断的和栈顶元素进行比较
            temperature = temperatures[i]

            # 如果栈顶元素存在并且当天的温度大于栈顶元素
            # 意味着栈顶元素等到了第一个温度比它更高的那一天
            # 它们的下标差就是栈顶元素等了多少天等到的更高温度的结果
            while stack and temperature > temperatures[stack[-1]]:

                # 首先获取栈顶元素的值,也就是每日温度的下标值
                preIndex = stack.pop()

                # 它们的下标差就是栈顶元素等了多少天等到的更高温度的结果,保存到输出数组 res 中
                res[preIndex] = i - preIndex


            # 再把当天的温度的下标值存放到栈中
            # 注意:是下标索引值
            stack.append(i)

        # 最后输出 res 数组即可
        return res

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(1)

  • 陈芷维 永久会员 2021年10月17日 上午8:31

    class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
    // method 1: 用stack实现
    // 1. 构建栈,存放每日温度的下标; 构建数组,存放结果
    Stack temp = new Stack();
    int[] result = new int[temperatures.length];
    // 2. 遍历温度数组,判断是否压栈,并输出结果
    int round = 0;
    for (int i = 0; i < temperatures.length; i++) {
    if (temp.isEmpty()) {
    temp.push(i);
    // System.out.println("round " + (round++) + ": " + i + ", " + temperatures[i]);
    } else {
    // 判断栈顶元素和当前元素的大小
    while (!temp.isEmpty() && (temperatures[temp.peek()] < temperatures[i])) {
    // 栈顶元素迎来更高温度,输出结果
    result[temp.peek()] = i – temp.peek();
    // System.out.println("result " + temp.peek() + ": " + result[temp.peek()]);
    int top = temp.pop(); // 弹出栈顶
    // System.out.println("pop:" + top);
    }
    temp.push(i);
    // System.out.println("round " + (round++) + ": " + i + ", " + temperatures[i]);
    }
    }
    // 弹出所有还在栈中的元素,其对应的结果为0
    while(!temp.isEmpty()) {
    result[temp.peek()] = 0;
    temp.pop();
    }
    return result;
    }
    }