代码

package com.xcrj;

import java.util.Arrays;

/**
 * 剑指 Offer II 038. 每日温度
 * 请根据每日 气温 列表 temperatures，重新生成一个列表，要求其对应位置的输出为：
 * 要想观测到更高的气温-温度更高
 * 至少需要等待的天数-最小日期，更大日期
 * 如果气温在这之后都不会升高，请在该位置用0 来代替。
 */
public class Solution38 {
    /**
     * 区别：使用 线性表 times[温度]=日期 记录温度对应的日期
     * 

     * 倒序寻找温度更高的最小日期
     * - 温度更高：temperatures[i] + 1~100
     * - 最小日期：times[温度]=日期 记录温度对应的日期
     * - 更大日期：倒序保证更大日期
     * 

     * 将日期和温度分开记录
     * - 记录温度：temperatures[日期]=温度
     * - 记录日期：times[温度]=日期
     * 

     * 已知：
     * - 温度 in [30,100]
     */
    public int[] dailyTemperatures1(int[] temperatures) {
        // 结果
        int[] rs = new int[temperatures.length];
        // 记录日期, 101是0度~100度
        int[] times = new int[101];
        // 最小日期
        Arrays.fill(times, Integer.MAX_VALUE);
        // 倒序
        for (int i = temperatures.length - 1; i >= 0; i--) {
            int minTime = Integer.MAX_VALUE;
            // 寻找温度更高
            for (int j = temperatures[i] + 1; j <= 100; j++) {
                // 的最小日期
                if (times[j] < minTime) {
                    minTime = times[j];
                }
            }
            // 记录结果
            if (minTime != Integer.MAX_VALUE) rs[i] = minTime - i;

            // times[温度]=日期
            times[temperatures[i]] = i;
        }

        return rs;
    }

    /**
     * 区别：使用 单调栈 记录stack{递减温度下标(日期)}
     * 

     * 栈存储更低温度的下标(日期)
     * - 温度更高：线性表temperatures[i] > temperatures[栈stack[top]]
     * - 最小日期：正序依次遍历线性表，依次比较单调栈
     * - 更大日期：正序依次遍历线性表
     * 

     * 单调栈：记录单调递增或单调递减的栈
     * 单调栈使用：遍历线性表，栈存储已经遍历过的元素，将栈中的元素与正在遍历的线性表中的第i个元素对比，更大的出栈
     */
    public int[] dailyTemperatures2(int[] temperatures) {
        // 结果
        int[] rs = new int[temperatures.length];
        // 单调栈
        int top = -1;
        int[] stack = new int[temperatures.length];
        // 遍历线性表
        for (int i = 0; i < temperatures.length; i++) {
            //  寻找温度更高
            while (top != -1 && temperatures[i] > temperatures[stack[top]]) {
                // 的最小日期
                int j = stack[top--];
                rs[j] = i - j;
            }
            // 入栈温度更低日期
            stack[++top] = i;
        }
        return rs;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

参考

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/iIQa4I/solution/mei-ri-wen-du-by-leetcode-solution-vh9j/
来源：力扣（LeetCode）