专栏首页健程之道力扣739——每日温度

力扣739——每日温度

这道题主要是找规律,优化的时候可以利用数据结构的特性(数组和栈)。

原题

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

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

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

原题url:https://leetcode-cn.com/problems/daily-temperatures/

解题

优先队列

如果正向思考的话,就是从前向后遍历,将温度存储在一个优先级队列中(小顶堆),队列中的结构需要记录温度和天数。

遍历时需要找到队列中最小的值是否大于当前温度,如果大于,则更新结果;如果小于,则将当前记录放入队列中。

接下来看看代码:

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 以温度为排序依据的小顶堆,温度越低越靠前
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.temperature));
        for (int index = 0; index < T.length; index++) {
            Node node = new Node();
            node.temperature = T[index];
            node.index = index;
            // 放入队列中
            queue.add(node);
            // 取队列中最小的元素
            Node newNode = queue.peek();
            // 如果队列中最低温度就是当前温度
            if (newNode.temperature == node.temperature) {
                // 说明queue中没有比当前温度低的天
                continue;
            }

            // 最低温度比当前低,满足情况
            while (newNode.temperature < node.temperature) {
                // 更新T,并且移除
                T[newNode.index] = node.index - newNode.index;
                queue.remove();
                newNode = queue.peek();
            }
        }

        // 队列中剩余的节点,都对应0
        Iterator<Node> iterator = queue.iterator();
        while (iterator.hasNext()) {
            Node node = iterator.next();
            T[node.index] = 0;
        }

        return T;
    }

    class Node {
        int temperature;
        int index;
    }
}

提交OK,时间复杂度为O(n),但小顶堆的更新也是需要时间的,因此还是有可以优化的地方。

数组

因为题目中给出了:每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数,所以我们可以用一个长度为100的数组存储气温对应的天数。

这样我们就需要从后向前遍历了,将气温对应的天数记录在数组中,这样每向前遍历一个,就遍历一次这个长度为100的数组,如果有比当前温度高的,则更新结果,否则就记为0。

虽然每次都要遍历一次长度为100的数组,但因为数组查询的时间复杂度为O(1),所以速度是很快的。接下来我们看看代码:

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 最终结果
        int[] result = new int[T.length];
        // 因为温度不超过100度,所以温度对应的天数存储在这个数组中
        int[] next = new int[101];
        Arrays.fill(next, Integer.MAX_VALUE);
        // 从后向前遍历
        for (int i = T.length - 1; i >= 0; --i) {
            // 比当前温度更高的下标
            int warmerIndex = Integer.MAX_VALUE;
            // 从next数组中查找比当前温度高的天数
            for (int t = T[i] + 1; t <= 100; ++t) {
                // 找出天数最小的一个
                if (next[t] < warmerIndex) {
                    warmerIndex = next[t];
                }
            }
            // 如果有找到,则更新result
            if (warmerIndex < Integer.MAX_VALUE) {
                result[i] = warmerIndex - i;
            }
            // 在next数组中记录当前的温度
            next[T[i]] = i;
        }
        return result;
    }
}

提交OK,这里其实就够了,但有没有其他更方便的数据结构呢?

我们主要想知道的,就是最近的比当前温度高的天数,这样的需求,感觉栈应该是可以满足的,因为先进后出。

我们还是从后向前遍历,在栈中存储气温的天数,当前遍历到的温度,如果比栈顶的存储的天数对应的温度高,那么栈中存储的是没有意义的;如果比它低,那么就可以更新结果了。

接下来看看代码:

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 用栈存储温度的下标
        Stack<Integer> stack = new Stack<>();
        // 最终的结果
        int[] result = new int[T.length];
        // 从后向前遍历
        for (int i = T.length - 1; i >= 0; i--) {
            // 如果当前温度大于栈顶的温度
            while (!stack.isEmpty() && T[i] >= T[stack.peek()]) {
                // 因为当前温度比栈顶存储的温度高,
                // 栈顶元素也没有存储的意义,所以出栈
                stack.pop();
            }
            // 如果栈为空,则结果为0
            // 如果栈不为空,则用当前栈顶存储的温度
            result[i] = stack.isEmpty() ? 0 : (stack.peek() - i);
            // 让当前的温度入栈
            stack.push(i);
        }

        return result;
    }
}

提交OK,时间复杂度和上面的方法相同,但空间复杂度理论上是会比上面小的。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要是找规律,优化的时候可以利用数据结构的特性(数组和栈)。

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode】739. 每日温度

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

    韩旭051
  • ​LeetCode 739:每日温度 Daily Temperatures

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

    爱写bug
  • LeetCode 739. 每日温度(单调栈)

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

    Michael阿明
  • 单调栈-LeetCode 739、287(单调栈,桶计数)

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

    算法工程师之路
  • LeetCode 739:每日温度(超容易理解的解法!!!)

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

    五分钟学算法
  • 每日温度

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

    用户7962184
  • top100习题

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

    黑白格
  • 单调栈入门+动画视频

    对于栈这种数据结构,相信大部分同学都会觉得很简单,它只有一个特性,那就是先进后出。

    ACM算法日常
  • 【leetcode刷题】T27-每日温度

    Given a list of daily temperatures T, return a list such that, for each day in t...

    木又AI帮

扫码关注云+社区

领取腾讯云代金券