2019-06-06.md

毎日一题 - 739.Daily Temperatures

信息卡片

• 时间：2019-06-06
• 题目链接：https://leetcode.com/problems/daily-temperatures/
• tag：Array Stack

题目描述

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].

参考答案

暴力，双层for循环。效率很低

1. 外层是‘当天’T[i]，内层是‘当天’之后T[j]；
2. 多少天之后比‘当天’温度高就是j-i；

时间复杂度O(n^2), 空间复杂度O(1)

参考JavaScript代码：

/**
 * @param {number[]} T
 * @return {number[]}
 * 双层for循环
 */
var dailyTemperatures = function(T) {
    let result = [];
    for(let i = 0; i < T.length; i++) {
        result[i] = 0;
        for(let j = i + 1; j < T.length; j++) {
            if (T[i] < T[j]) {
                result[i] = j - i;
                break;
            }
        }
    }
    return result;
};

使用栈,单调递减栈

1. for循环遍历数组，栈存T的下标i，返回结果数组result；
2. 拿栈顶元素peek与i比较，T[peek] >= T[i]则将i入栈，T[peek] < T[i]则栈顶值(原数组下标)位置的天数就是result[peek] = i - peek；
3. 栈顶元素出栈；
4. 重复2，3两步；

时间复杂度O(n), 空间复杂度O(n)

参考JavaScript代码：

/**
 * @param {number[]} T
 * @return {number[]}
 * 递减栈；
 */
var dailyTemperatures = function(T) {
    let stack = [];
    let result = [];
    for (let i = 0; i < T.length; i++) {
        result[i] = 0;
        while(stack.length > 0 && T[stack[stack.length - 1]] < T[i]) {
            let peek = stack.pop();
            result[peek] = i - peek;
        }
        stack.push(i);
    }
    return result;
};

Python3 代码：

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack = []
        ans = [0] * len(T)
        for i in range(len(T)):
            while stack and T[i] > T[stack[-1]]:
                peek = stack.pop(-1)
                ans[peek] = i - peek
            stack.append(i)
        return ans

优秀解答

暂缺