Re: [閒聊] 每日LeetCode

[pandix (麵包屌)]

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
推 wwndbk: 蛤?
→ PogChampLUL: 龍大只發優文，不歪樓，不引戰，拜託你滾遠一點
推 sustainer123: 大師
推 Rushia: 大師
推 moonoftree: 大師
推 NTHUlagka: 大師