每日题解:LeetCode 739. 每日温度

Author Avatar
清水雅然君 06月 11,2020

题目地址
个人博客地址

题目描述

  1. 每日温度
    请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。

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

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

解法

JAVA

class Solution {
    public int[] dailyTemperatures(int[] T) {
    int len = T.length;
        int[] ans = new int[len];
        //73, 74, 75, 71, 69, 72, 76, 73
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() &&  T[stack.peek()]< T[i]) {
                //处理元素
                int num=i-stack.peek();
                int index=stack.pop();
                ans[index]=num;
            }
            stack.push(i);
        }
        return ans;
    }
}

CPP

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

        return  ans;
    }
};

解题思路

单调栈

为什么 [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 。

这题可以和之前的状图中最大的矩形结合一起理解,使用了栈,维护从栈底到栈顶的下标对应的温度列表中的温度依次递减。
先遍历数组,如果栈为空,我们就将下标i入栈,如果栈不为空,我们将栈顶的元素和当前的T[i]比较,如果当前元素小于栈顶元素,将当前元素压进栈;如果T[i] 大于栈顶的元素,将栈顶元素移除,同时得到升高的天数,即当前的i-栈顶下标,然后继续栈顶元素比较,直到栈元素清空或者大于当前元素。

 Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < len; i++) {
        //当前元素大于栈顶元素,如74>73,开始计算
            while (!stack.isEmpty() &&  T[stack.peek()]< T[i]) {
                //获取下标差值
                int num=i-stack.peek();
                //移除栈顶元素。同时将返回结果的赋值差值
                int index=stack.pop();
                ans[index]=num;
            }
            stack.push(i);
        }

当前这里也可以使用暴力方法解决,使用类似冒泡排序,可以参考官方题解的写法

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int length = T.length;
        int[] ans = new int[length];
        int[] next = new int[101];
        Arrays.fill(next, Integer.MAX_VALUE);
        for (int i = length - 1; i >= 0; --i) {
            int warmerIndex = Integer.MAX_VALUE;
            for (int t = T[i] + 1; t <= 100; ++t) {
                if (next[t] < warmerIndex) {
                    warmerIndex = next[t];
                }
            }
            if (warmerIndex < Integer.MAX_VALUE) {
                ans[i] = warmerIndex - i;
            }
            next[T[i]] = i;
        }
        return ans;
    }
}