Version: Next

739. 每日温度

难度 中等

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

栈

找每个元素右侧第一个比自己大的元素

public class _739每日温度 {
    public int[] dailyTemperatures(int[] T) {
        if (T.length == 1) return new int[]{0};
        // 维护一个单调递减栈
        Stack<Integer> stack = new Stack<>();

        // 如果新值 比 栈顶大，出栈
        // 出栈元素 右侧第一个大元素 就是当前元素i
        int[] res = new int[T.length];

        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int delta = i - stack.peek();
                res[stack.pop()] = delta;
            }

            stack.push(i);
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {73, 74, 75, 71, 69, 72, 76, 73};
        int[] res = new _739每日温度().dailyTemperatures(nums);

        for (int re : res) {
            System.out.println("re = " + re);
        }
    }
}

倒推法

类似动态规划
指针 i 用来扫描所有元素，从右往左扫描（i 递减），一开始 i 指向倒数第二个元素
对于每一个 i 一开始令 j = i + 1 即，i 右侧的那个元素
如果 T[i] < T[j] ：那么 values[i] = j - i；然后 i--
如果 T[i] == T[j]
如果 values[j] ==0，那么 values[i] =0, i--
那么 values[i] = values[j] + j - i，i--
如果 T[i] > T[j]
如果 values[j] == 0，则 values[i] == 0 ， i--
如果 values[j] != 0，则 j = j + values[j] （跳到当前 j 指向元素大的右侧第一个元素），重新进入 步骤 1

public int[] dailyTemperaturesDp(int[] T) {
    if (T.length == 1) return new int[]{0};

    int[] values = new int[T.length];

    for (int i = T.length - 2; i >= 0; i--) {
        int j = i + 1;

        while (true) {
            if (T[i] < T[j]) {
                values[i] = j - i;
                break; // aka i--
            } else if (T[i] == T[j]) {
                if (values[j] == 0) values[i] = 0;
                else values[i] = values[j] + j - i;
                break;
            } else {
                if (values[j] == 0) {
                    values[i] = 0;
                    break;
                } else j = j + values[j];
            }
        }
    }

    return values;
}

精简

对于每一个 i，一开始令 j = i + 1
如果 T[i] < T[j]，那么 values[i] = j - i，然后 i--
如果 values[j] == 0，那么 values[i] = 0，然后 i--
否则，设置 j = j + values[j]，回到步骤 1

739. 每日温度#

栈#

倒推法#

精简#

739. 每日温度

栈

倒推法

精简