Re: [閒聊] 每日LeetCode已回收
901. Online Stock Span
龍大只發優文，不歪樓，不引戰，拜託你滾遠一點。
一個判斷是不是優文的指標是看推文數有沒有比之前的多。
幫龍大找出每篇文章的推文比之前連續幾篇文章多，請你認真對待這個要求……
Example 1:
Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]
簡單說就是每發一篇文就往回看之前的文章有沒有小於等於他，有就繼續檢查直到大於他
以上面[100,80,60,70,60,75,85] 中的 75 為例
先比自己 75, 75 <= 75 -> 60 <= 75 -> 70 <= 75 -> 60 <= 75 -> 80 > 75
所以有連續四篇文章小於等於他 就輸出四
後面的 85 就有連續六篇都小於等於他只有 100 大於他
思路:
1.可以先想下一個進來的數字要怎麼判斷，像是上面的 75 output 4 如果是已知
如果下一個進來的數字 < 75 -> 輸出 1，因為他往回第一個 75 就比他大了
如果 > 75 -> 那就直接知道 75 前四個數字一定都小於他，75 前第五個數字則不一定
所以就繼續判斷 75 前第五個數字和新數字的大小，同時可以把他的 output += 4
代表 75 和他後面的三個數字都比新數字小
2.可以用陣列，要知道下個要和誰比直接 index 減去他的 output 就好
也可以用 stack，因為對 75 來說他之前小於他的數字已經是不需要的資訊了
等於是可以維護一個遞減的 stack，新數字進來時 pop 掉那些比他小的數字
只是除了數字也要順便記 output，這樣才能知道總共有多少數字比他小
3.Python code:
class StockSpanner:
def __init__(self):
self.stk = []
def next(self, price: int) -> int:
span = 1
while self.stk and self.stk[-1][0] <= price:
span += self.stk.pop()[1]
self.stk.append((price, span))
return span
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.221.15 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667961772.A.911.html
推
11/09 10:43,
3年前
, 1F
11/09 10:43, 1F
→
11/09 10:44,
3年前
, 2F
11/09 10:44, 2F
推
11/09 10:53,
3年前
, 3F
11/09 10:53, 3F
推
11/09 10:55,
3年前
, 4F
11/09 10:55, 4F
推
11/09 12:44,
3年前
, 5F
11/09 12:44, 5F
推
11/09 22:57,
3年前
, 6F
11/09 22:57, 6F
討論串 (同標題文章)
完整討論串 (本文為第 92 之 719 篇)：