力扣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;
    }
}