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