Re: [閒聊] 每日LeetCode
有印象耶這題 精華區居然還找的到 Rushia整理的好好==
---
作者: pandix (麵包屌) 看板: Marginalman
標題: Re: [閒聊] 每日LeetCode
時間: Sun Dec 18 13:24:04 2022
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
---
今天寫的
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stk = []
res = [0]*len(temperatures)
for i, t in enumerate(temperatures):
while stk and stk[-1][1] < t:
res[stk[-1][0]] = i - stk[-1][0]
del stk[-1]
stk.append((i, t))
return res
多存了溫度進 stack 裡
對齁 有 index 直接撈就好了幹嘛存 變笨了==
--
沒人在乎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.165.44.120 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1706681676.A.27E.html
→
01/31 14:15,
2年前
, 1F
01/31 14:15, 1F
推
01/31 14:16,
2年前
, 2F
01/31 14:16, 2F
→
01/31 14:16,
2年前
, 3F
01/31 14:16, 3F
推
01/31 14:20,
2年前
, 4F
01/31 14:20, 4F
推
01/31 14:21,
2年前
, 5F
01/31 14:21, 5F
討論串 (同標題文章)
完整討論串 (本文為第 637 之 719 篇)：