0739._Daily_Temperatures.md

739. Daily Temperatures

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/daily-temperatures/description/

内容描述

Given a list of daily temperatures, produce a list 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 temperatures = [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].

解题方案

思路 1 - 时间复杂度: O(NW)- 空间复杂度: O(N+W)*****

Next Array 方法

温度只有[30,100]，搞一个102长度的list记一下

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        nxt = [float('inf')] * 102
        res = [0] * len(temperatures)
        for i, temperature in enumerate(temperatures[::-1]):
            # Use 102 so min(nxt[t]) has a default value
            i = len(temperatures) - 1 - i
            warmer_index = min(nxt[t] for t in range(temperature+1, 102)) # 最近的一个warmer天的idx
            if warmer_index < float('inf'):
                res[i] = warmer_index - i # 第一个warmer天的idx与当前idx的差即为等几天
            nxt[temperature] = i
        return res

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(W)******

单调栈, 牢记找小于大于问题

beats 87.24%

class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        res = [0] * len(temperatures)
        stack = [] # indexes from hottest to coldest
        for i in range(len(temperatures) - 1, -1, -1):
            while stack and temperatures[i] >= temperatures[stack[-1]]:
                stack.pop()
            if stack:
                res[i] = stack[-1] - i # 第一个warmer天的idx与当前idx的差即为等几天
            stack.append(i)
        return res