Python每日溫度

假設我們有一列每日溫度T，我們需要返回一個列表，對於輸入中的每一天，顯示我們需要等待多少天才能等到更高的溫度。如果未來沒有更高溫度的一天，則儲存0。例如，如果T = [73, 74, 75, 71, 69, 72, 76, 73]，輸出將是[1, 1, 4, 2, 1, 1, 0, 0]。

為了解決這個問題，我們將遵循以下步驟：

• ans := 一個與T大小相同的陣列，並將其填充為0
• 定義一個棧，並將0插入棧中，i := 1
• 當i < T的長度時
  • 當棧元素個數不為0且T[i] > T[棧頂元素]時
    • index := 棧頂元素
    • ans[index] := i – index
    • 從棧中刪除頂元素
  • 如果棧的長度為0或T[i] <= T[棧頂元素]
    • 將i插入棧中
  • i增加1
• 返回ans

示例(Python)

讓我們看看下面的實現來更好地理解：

 線上演示

class Solution(object):
   def dailyTemperatures(self, T):
      ans = [0 for i in range(len(T))]
      stack = []
      stack.append(0)
      i=1
      while i <len(T):
         while len(stack) and T[i]>T[stack[-1]]:
            index = stack[-1]
            ans[index] = i-index
            stack.pop()
         if not len(stack) or T[i]<=T[stack[-1]]:
            stack.append(i)
         i+=1
      return ans
ob1 = Solution()
print(ob1.dailyTemperatures([73,74,75,71,69,72,76,73]))

輸入

[73,74,75,71,69,72,76,73]

輸出

[1, 1, 4, 2, 1, 1, 0, 0]

Arnab Chakraborty

更新於：2020年4月29日

845 次瀏覽

開啟您的職業生涯

透過完成課程獲得認證

開始學習