leetcode_739毎日温度

タイトル
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].
日语原文:毎日の温度リストTが知られていますが、各要素(現在の温度値)と次の現在の温度よりも高い要素とのインデックス(日数)の差を求めます.
解法1

class Solution:
    def dailyTemperatures(self, T):
        """
            ：
        1.            ,
                              ，       ，              ，
                          ，             ，        
        2.  ：           ，         ，              ;
        :param T:
        :return:
        """
        ans = [0] * len(T)  #          
        queue = []  # queue          `        `
        for i, val in enumerate(T):
            # len(queue) 1    ,            ；
            # queue[-1]        
            # T[queue[-1]]   queue        T      
            while len(queue) > 0 and val > T[queue[-1]]:
                pre_i = queue.pop()
                ans[pre_i] = i - pre_i
            queue.append(i)  #           
        return ans


RES = Solution().dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])
print(RES)

解法2

"""
    ，          ，       。                 ，     0。
          ，         ，       1，         ，        
      0，          ，              0。
           ，    i      ，      i+1       

  ：

-  T[i] < T[i+1]，  res[i]=1；

-  T[i] > T[i+1]
  - res[i+1]=0，  res[i]=0;

  - res[i+1]!=0，    T[i] T[i+1+res[i+1]]（   i       i+1            ）

"""

def daily_temperatures(self, T):
    """
    :type T: List[int]
    :rtype: List[int]
    """
    res = [0] * len(T)

    def get_res(i, j):
        if T[i] < T[j]:
            return j - i
        else:
            if res[j] == 0:
                return 0
            else:
                return get_res(i, j + res[j])

    for i in range(len(T) - 2, -1, -1):
        res[i] = get_res(i, i + 1)

    return res

解法2_小結

k-1元素とk元素を比較し、k元素がk-1元素より大きい場合は、すべて相談しやすく、両者を下付きで減算するだけで、 1

は、第1の条件を満たさない後、k元素のresが0である場合、次はより高い温度がないことを意味し、対応する位置は0

に直接付与される.

第2の条件を満たさない場合、第k-1要素とk+res[k]要素を再帰的に呼び出し、k-1要素より大きい要素が見つかるまで、両者の下付き文字を直接減算すれば

である.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/daily-temperatures著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.