# Leetcode --- Online Stock Span

## 901. Online Stock Span
### Description:
Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock's price for the current day.

The span of the stock's price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today's price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

:::info
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]
Explanation:
First, S = StockSpanner() is initialized. Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price.
:::
:::warning
Note:

Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
There will be at most 10000 calls to StockSpanner.next per test case.
There will be at most 150000 calls to StockSpanner.next across all test cases.
The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.
:::


### 解法條列
1. 暴力解 O(n), n為輸入price的次數
2. 優化解 O(1)

### 解法細節
想像成peak(尖峰)的形成。
若當前高度大於之前的peak, 則合併掉之前的peak。
若是當前高度下降的話, 則形成一個新的peak。

歷史peak值只會越來越少, 因為若出現大的peak會合併小的peak
所以會使用資料結構:
:::success
monotonic stack
:::

### Python Solution
優化解

class StockSpanner:
    def __init__(self):
        self.peak_stack_value = [] # 維持遞減
        self.peak_stack_sum = [] # peak間的元素數量和
        
        self.current_peak_value = float('-inf')
        self.current_sum = 0
    def next(self, price: int) -> int:
        if price >= self.current_peak_value:
            self.current_peak_value = price
            self.current_sum += 1
            while(self.peak_stack_value and self.current_peak_value >= self.peak_stack_value[-1]):
                self.peak_stack_value.pop()
                self.current_sum += self.peak_stack_sum.pop()         
        else:
            self.peak_stack_value.append(self.current_peak_value)
            self.peak_stack_sum.append(self.current_sum)
            self.current_peak_value = price
            self.current_sum = 1

        return self.current_sum
        
        
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)       

---

def __init__(self):
    self.peak_stack_value = [] # 維持遞減
    self.peak_stack_sum = [] # peak間的元素數量和

    self.current_peak_value = float('-inf')
    self.current_sum = 0

peak_stack_value 記錄各個peak的值, 呈現遞減
peak_stack_sum 記錄peak到peak間元素的數量
若current peak value大於之前的peak, 則取代之前的peak, 並將sum合併

current_peak_value為比之前的peak小, 但又比之前輸入的price還大的值
current_sum為比輸入price值還小的元素數量, 也就是回傳值

---

def next(self, price: int) -> int:
    if price >= self.current_peak_value:
        self.current_peak_value = price
        self.current_sum += 1
        while(self.peak_stack_value and self.current_peak_value >= self.peak_stack_value[-1]):
            self.peak_stack_value.pop()
            self.current_sum += self.peak_stack_sum.pop()         
    else:
        self.peak_stack_value.append(self.current_peak_value)
        self.peak_stack_sum.append(self.current_sum)
        self.current_peak_value = price
        self.current_sum = 1

    return self.current_sum

以一個if else判斷完成對current_sum的更新

---

if price >= self.current_peak_value:
        self.current_peak_value = price
        self.current_sum += 1
        while(self.peak_stack_value and self.current_peak_value >= self.peak_stack_value[-1]):
            self.peak_stack_value.pop()
            self.current_sum += self.peak_stack_sum.pop()    

若price大於當前current_peak_value,
則更新current_peak_value和current_sum

若是price也比之前的peak值還大的話, 移除peak值
並把那個peak值之前的元素數量合併在當前sum中

---

else:
    self.peak_stack_value.append(self.current_peak_value)
    self.peak_stack_sum.append(self.current_sum)
    self.current_peak_value = price
    self.current_sum = 1

若price小於當前current_peak_value, 則代表產生了新的peak。
將peak value以及之前的元素數量記錄起來。
初始化當前peak value以及sum。

---
可改進部分為記憶體空間, 但可能會是一個時間與空間的trade-off。

###### tags: `leetcode` `array` `medium` `stack` `monotic stack`