leetcode:毎日温度(単調スタック)

764 ワード

同様に、柱図で最大の長方形(単調スタック*)
毎日の気温リストに基づいて、リストを再生成してください.対応位置の出力は,より高い気温を観測するためには,少なくとも待機日数が必要である.この後も気温が上がらない場合は、この位置で0で代用してください.
たとえば、temperatures=[73,74,75,71,69,72,76,73]のリストが与えられ、あなたの出力は[1,1,4,2,1,1,0,0]であるべきです.
ヒント:気温リストの長さの範囲は[1,30000]です.各気温の値は華氏度であり、[30,100]の範囲内の整数である.
単調なスタックの構想でこの問題は比較的に簡単で、しかもO(n)の時間の内にこの問題を解決することができます
class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stacks = []
        n = len(T)
        result = [0 for x in range(n)]
        for i in range(n):
            while stacks != [] and T[i] > T[stacks[-1]]:
                result[stacks[-1]] = i - stacks[-1]
                stacks.pop()
            stacks.append(i)
        return result