题目描述

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

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

题目分析

哈希表

题目温度是有范围的，最高100度，可以每个温度最早出现的位置。
对于每天，都可以遍历从当前温度到100度之间，最小的位置。
时间复杂度 O(m * n)，n为数组长度，m为温度范围

单调栈

使用栈保存数据，每次插入数据前，先将所有更小的元素出栈，保持从栈底到栈顶数据的单调递减。对于栈内数据来说，出栈时对应的数据即为下一个更高温度。
实际代码中，栈内存储下标即可，通过原数组读取数据。
每个元素最多入栈一次出栈一次，时间复杂度 O(n)

Java

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

Kotlin

fun dailyTemperatures1(temperatures: IntArray): IntArray {
    val map = IntArray(101)
    val ans = IntArray(temperatures.size)
    for (i in temperatures.indices.reversed()) {
        map[temperatures[i]] = i
        for (t in (temperatures[i] + 1)..100) {
            if (map[t] > 0) {
                ans[i] = if (ans[i] > 0 && ans[i] < map[t] - i) ans[i] else map[t] - i
            }
        }
    }
    return ans
}

fun dailyTemperatures2(temperatures: IntArray): IntArray {
    val stack = LinkedList<Int>()
    val ans = IntArray(temperatures.size)
    for (i in temperatures.indices) {
        while (!stack.isEmpty()) {
            val index = stack.peek()
            if (temperatures[index] < temperatures[i]) {
                stack.pop()
                ans[index] = i - index
            } else {
                break
            }
        }
        stack.push(i)
    }
    return ans
}