力扣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) { // 以温度为排序依据的小顶堆,温度越低越靠前 PriorityQueuequeue = 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 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) { // 用栈存储温度的下标 Stackstack = 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,时间复杂度和上面的方法相同,但空间复杂度理论上是会比上面小的。
总结
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要是找规律,优化的时候可以利用数据结构的特性(数组和栈)。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。
https://death00.github.io/
公众号:健程之道