【LeetCode】739. 每日温度

简单来说，就是找再过几天，温度超过今天。如果之后的温度都低于今天，置为0

我的做法是直接按照题意来，时间效率上有点低。

public class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 就按照题意来吧
        int[] res = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            // 遍历数组
            int tmp = 0;
            for (int j = i + 1; j < T.length; j++) {
                if (T[j] > T[i]) {
                    tmp = j-i;
                    break;
                }
            }
            res[i] = tmp;
        }
        return res;
    }
}

官方解法一：/思路是这样的，我建立一个next数组，next数组的序号为温度值，数值为T中的序号，也就是天数，我从后向前遍历数组T，假设遍历到一个温度为60摄氏度，我就在next中，查看61，62，…100的数值，也就是天数。找到天数的最小值，这样就找到了再过几天，温度能超过60摄氏度。

class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 思路是这样的，我建立一个next数组，
        // next数组的序号为温度值，数值为T中的序号，也就是天数
        // 我从后向前遍历数组T，假设遍历到一个温度为60摄氏度
        // 我就在next中，查看61，62，.....100的数值，也就是天数。找到天数的最小值
        // 这样就找到了再过几天，温度能超过60摄氏度。
        int[] next = new int[101];//温度范围30~100
        int[] res = new int[T.length];
        Arrays.fill(next, Integer.MAX_VALUE);
        for (int i = T.length - 1; i >= 0; i--) {
            int tem = T[i];
            int min = Integer.MAX_VALUE;
            for (int j = tem + 1; j < 101; j++) {
                min = Math.min(min, next[j]);
            }
            if (min != Integer.MAX_VALUE) res[i] = min - i;
            next[tem] = i;
        }
        return res;
    }
}

官方的第二个解法：使用一个辅助栈，时间复杂度是最小的，但是可能测试用例不够多，导致时间大于官方的第一个解法。

public class Solution {
    public int[] dailyTemperatures(int[] T) {
        // 这个思路利用一个栈结构来实现。
        // 从后向前遍历T，假设遍历到温度50，我看看栈顶的序号对应的温度是不是大于50
        // 如果小于等于50就pop，直到找到大于50的那个序号，或者栈为空了。
        // 如果此时栈为空，那么res置为0，否则置为序号相减
        // 将50这个序号push进栈。
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[T.length];
        for (int i = T.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && T[stack.peek()] <= T[i]) {
                stack.pop();
            }
            res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return res;
    }
}