【NO.100】LeetCode HOT 100—739. 每日温度

题目：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]

解题

方式一：暴力求解

最简单莫过于双重循环暴力求解，思路：从当前下标 i 开始往后寻找第一个比其大的数，记录其下标 j ，那 answer[i] = j - i ，不多说，直接上代码：

/**
 * 时间复杂度：O(n^2)
 * 空间复杂度：O(n)
 */
public int[] dailyTemperatures(int[] temperatures) {
    int[] answer = new int[temperatures.length];
    for (int i = 0; i < temperatures.length - 1; i++) {
        for (int j =  i + 1; j < temperatures.length; j++) {
            if (temperatures[j] > temperatures[i]) {
                answer[i] = j - i;
                break;
            }
        }
    }
    return answer;
}

方式二：单调栈

思路：

• 可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。
• 正向遍历温度列表，对于温度列表中的每个元素 temperatures[i] ,

• 如果栈为空，则直接将 i 进栈，
• 如果栈不为空，则比较栈顶元素 index 对应的温度和当前温度 temperatures[i]的大小，如果当前温度大于栈顶元素对应的温度，则将栈顶元素移除，并记录栈顶元素 index 对应的等待天数为 i - index

/**
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
public int[] dailyTemperatures(int[] temperatures) {
    int length = temperatures.length;
    int[] answer = new int[length];
    // 单调栈
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < length; i++) {
        int temp = temperatures[i];
        // 栈不空，比较当前温度和栈顶元素对应的温度的大小
        while (!stack.isEmpty() && temp > temperatures[stack.peek()]) {
            // 碰见温度更高的，计算差值，得到结果
            answer[stack.peek()] = i - stack.peek();
            stack.pop();
        }
        // 栈为空，当前下标放进去
        stack.push(i);
    }

    return answer;
}