ヾ(･∀･)ﾉ
嗨，我是wec，今天是DAY 29。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

給定一個整數數組temperatures，表示每天的溫度，請返回一個數組answer，其中answer[i]是距離i天以後，才會出現比temperatures[i]更高的溫度的天數。如果沒有更高的溫度，則對應位置設為0。

🔎 解題思路＆程式碼

1️⃣ 堆疊

第1步： 創建一個和temperatures相同大小的陣列answer，初始值為0。
第2步： 堆疊中儲存index，表示等待找到比當前溫度更高的未來天數。
第3步： 如果當前溫度比堆疊頂部的索引對應的溫度高，從堆疊中彈出索引，並計算兩者之間的天數差，存入 answer對應位置，然後將當前天數索引推入堆疊中。
第4步： 堆疊中剩餘的index，表示這些天沒有更高溫度，因此answer中的值保持為0。
程式碼：

def daily_temperatures(temperatures)
  answer = Array.new(temperatures.size, 0)
  stack = []

  temperatures.each_with_index do |temp, index|
    while !stack.empty? && temp > temperatures[stack.last]
      prev_index = stack.pop
      answer[prev_index] = index - prev_index
    end
    stack.push(index)
  end

  answer
end

🔎 總結

時間複雜度

堆疊： O(n)，n是temperatures的長度
➡️ 這題用到了單調堆疊(Monotonic Stack)的方法!簡單來說就是遞增遞減的擺放方式，但是基於LIFO特性，想要拿出來的順序是遞增，那麼放進去時就得從大的開始放。那麼這題我們用了一個遞減的堆疊，這樣我們就可以追蹤破紀錄的高溫，遇到比堆疊中最上層還高的溫度就可以馬上做更新的動作d(-∀-●)。

那麽，以上就是今天的內容！

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃好市多牛肉捲。
明天要說：Ruby精選刷題！Medium路跑LAST DAY!!(>∀･)⌒☆