力扣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，时间复杂度和上面的方法相同，但空间复杂度理论上是会比上面小的。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题主要是找规律，优化的时候可以利用数据结构的特性（数组和栈）。