LeetCode:739. Daily Temperatures

LeetCode:739. Daily Temperatures

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

温度値リストのセットが与えられ、各位置iについて、その位置温度よりも高い最も近い次の位置が求められる.
考え方1:暴力の解
後ろから前へ遍歴し、2人の哨兵でそれぞれ最低温度位置と最高温度位置を指した.

現在の温度が最低温度より小さい場合、後のすべての温度が現在の温度より大きいことを示し、1日でより暖かい温度に達することができる.

現在の温度が最大温度より大きい場合、必要な日数は0です.

であり、最低温度と最高温度の間の温度は、後のすべての温度を巡って最も近いより暖かい温度位置を見つける必要がある.

この解法は正しいがACはできない.参考にしてください.
Pythonコード実装

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        l = len(T)
        res = [0]*l
        minPos = l-1
        maxPos = l-1
        for i in range(l-2, -1, -1):
            if (T[i] < T[minPos]):
                res[i] = 1
                minPos = i
            elif (T[i] > T[maxPos]):
                res[i] = 0
                maxPos = i
            else:
                for j in range(i,l):
                    if(T[j] > T[i]):
                        res[i] = j-i
                        break
        return res

リスト全体が長い場合は、後のすべての日数を巡回するたびに時間がかかります.上記の方法を最適化すると、ハッシュ法を用いて各温度の位置を保存することを考慮し、ある位置において、現在位置の温度値から100度までのすべての温度を遍歴し、その温度より大きく、位置が-1でない最初の位置を見つけ、現在温度の位置を更新すればよい.
Pythonコード実装

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        l = len(T)
        res = [0]*l
        #                 
        tPos = [-1]*101
        for i in range(l-1, -1, -1):         
            #           100   
            for j in range(T[i],101):
                #                -1，          
                if(tPos[j] >= 0 and j > T[i]):  
                    #    0         ，   
                    if (res[i] ==0 or res[i] > (tPos[j]-i)):
                        res[i] = tPos[j]-i 
   
            #     
            tPos[T[i]] = i
        return res

構想二:スタック
また、スタックを使用して、現在の温度値から最大温度値までの昇順リスト区間(スタックトップ最小)を保存し、現在の位置温度がスタックトップ温度より大きい場合はスタックトップをポップアップし、現在の位置温度がスタックトップより小さい場合は直接スタックに入ります.
Pythonコード実装

class Solution(object):
    def dailyTemperatures(self, T):
        ans = [0] * len(T)
        stack = [] #indexes from hottest to coldest
        for i in range(len(T) - 1, -1, -1):
            while stack and T[i] >= T[stack[-1]]:
                stack.pop()
            if stack:
                ans[i] = stack[-1] - i
            stack.append(i)
        return ans

T=[73,74,75,71,69,72,76,73]を例にとると、

が最初に73を訪問したとき、スタックは空で、直接スタックに入り、スタックは[73].

は76,76>73にアクセスし、スタックトップ要素73をポップアップし、76をスタックに入れ、スタックは[76]である.

は72にアクセスし、72はスタックトップ要素76より小さいので、72に対応する最小日数は1であり、72をスタックに入れ、スタックは[72,76]である.

は69にアクセスし、69はスタックトップ要素72より小さいので、69に対応する最小日数は1であり、69をスタックに入れ、スタックは[69,72,76]である.

を順次類推し,最終解を得た.

THE END.