推 Rushia: 大師 12/18 13:27
→ ririoshi: 大師 12/18 13:28
→ Rushia: 我寫的也90%像 懶得貼了 12/18 15:26
推 NTHUlagka: 大師 12/18 21:31
739. Daily Temperatures
給你每天的氣溫，要你對每天算出到下一次氣溫比他高要隔幾天
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
以第三天的75為例，下次比他高是76 -> 中間隔了四天
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
思路:
1.這種找下個比他大的題型可以用 monotonic stack
維護一個遞減的 stack，看新加入的人有沒有機會更新前面的人
如果 stack[-1] 比新加入的小 代表 stack[-1] 後遇到第一個比他大的人就是新加入的
這時候就 pop 並且結算 stack[-1] (因為他找到第一個比他大的了)
直到 stack[-1] 比大於等於新加入的 這時候就能 append 他
整個 stack 依然會維持遞減
2.隔幾天就是要看 index 差多少，所以 stack 要存 index
Python code:
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stk = []
res = [0]*len(temperatures)
for i, t in enumerate(temperatures):
while stk and temperatures[stk[-1]] < t:
res[stk[-1]] = i-stk[-1]
del stk[-1]
stk.append(i)
return res
最近好冷
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.199.7 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671341048.A.286.html
※ 編輯: pandix (111.251.199.7 臺灣), 12/18/2022 13:26:38