【遍历, 分类讨论, 单调栈, 暴力】每日温度

题目

739. 每日温度

---

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

解题

方法一：暴力 模拟 遍历

思路

双层遍历，第一层遍历 temperatures 中的每一天(i)，第二层从第 i 天之后的一天开始(j)遍历之后的每一天，如果有比第 i 天温度高的第 j 天(temperatures[j] > temperatures[i])则在答案数组中第 i 天的位置赋上两天的差值(j - i)。

代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (temperatures[j] > temperatures[i]) {
                    ans[i] = j - i;
                    break;
                }
            }
        }
        return ans;
    }
}

方法二：反向遍历 分类讨论

思路

从最后一天推到第一天，因为最后一天显然不会再有升高的可能，结果直接为 0。 再看倒数第二天的温度，如果比倒数第一天低，那么答案显然为 1，如果比倒数第一天高，又因为倒数第一天之后温度不会再升高，对应的结果为0，所以倒数第二天的结果也应该为0。

由此可得出规律，要求出第 i 天对应的结果，只需要知道第 i+1 天对应的结果就可以：

• 若 T[i] < T[i+1]，那么 ans[i]=1
• 若 T[i] >= T[i+1]：
  • 若 ans[i+1] == 0，那么 ans[i]=0
  • 若 ans[i+1] != 0，那就比较 T[i] 和 T[i+1+ans[i+1]]（第 i 天的温度与比第 i+1 天高的那天的温度进行比较）

代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] ans = new int[len];
        ans[len - 1] = 0;
        outer: for (int i = len - 2; i >= 0; i--) {
            if (temperatures[i] < temperatures[i + 1]) ans[i] = 1;
            else {
                if (ans[i + 1] == 0) ans[i] = 0;
                else {
                    int j = i + 1 + ans[i + 1];
                    while (j < len) {
                        if (temperatures[i] < temperatures[j]) {
                            ans[i] = j - i;
                            break;
                        } else if (ans[j] == 0) {
                            ans[i] = 0;
                            continue outer;
                        }
                        j += ans[j];
                    }
                }
            }
        }
        return ans;
    }
}

优化

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] ans = new int[len];
        ans[len - 1] = 0;
        for (int i = len - 2; i >= 0; i--) {
            for (int j = i + 1; j < len; j += ans[j]) {
                if (temperatures[i] < temperatures[j]) {
                    ans[i] = j - i;
                    break;
                } else if (ans[j] == 0) {
                    ans[i] = 0;
                    break;
                }
            }
        }
        return ans;
    }
}

方法三：单调递减栈

思路

维护一个储存下标的单调栈，从栈底到栈顶的下标对应的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

正向遍历温度列表，对于温度列表中的每个元素 T[i]：

• 如果栈为空，则直接将 i 进栈
• 如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 T[prevIndex] 和当前温度 T[i]，如果 T[i] > T[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。

为什么可以在弹栈的时候更新 ans[prevIndex] 呢？因为在这种情况下，即将进栈的 i 对应的 T[i] 一定是 T[prevIndex] 右边第一个比它大的元素，试想如果 prevIndex 和 i 有比它大的元素，假设下标为 j，那么 prevIndex 一定会在下标 j 的那一轮被弹掉。

由于单调栈满足从栈底到栈顶元素对应的温度递减，因此每次有元素进栈时，会将温度更低的元素全部移除，并更新出栈元素对应的等待天数，这样可以确保等待天数一定是最小的。

代码

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        Deque<Integer> monoStack = new LinkedList<>();
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            while (!monoStack.isEmpty() &&
                   temperatures[i] > temperatures[monoStack.peek()]) {
                int prevIdx = monoStack.pop();
                ans[prevIdx] = i - prevIdx;
            }
            monoStack.push(i);
        }
        return ans;
    }
}