Leetcode題解 Python & C#：五月挑戰DAY19 Online Stock Span

做一個 StockSpanner 收集每日價格資訊 price (int)，並有設方法 next() 輸入 price ，回傳當前 price 是幾日新高。

對於這樣的問題，要想會不會用上 遞增數列 的觀念，這是這類題的一種數學思維，想通就會做。

(遞增數列的典型倒是沒有想到有什麼特徵可以快速抓出該用這個概念)

如果前面不超過price(<= price)，那麼就把前方的紀錄丟掉。如果沒資料可丟，代表目前是紀錄中最大的。

用一個計數 count，把用 next() 次數保留下來，就可以其減出當前price是幾日新高。(若沒紀錄，則 count - 0)

並且把 price 跟 count 添加到紀錄中，price跟count的紀錄代表前方沒有比price更高的。

官方寫法用 weight ，省下了 1 空間，但功能跟 count 都是記錄次數的。

Python

class StockSpanner:

    def __init__(self):
        self.prices = []
        self.count = 0


    def next(self, price: int) -> int:
        self.count += 1
        result = self.count
            
        while self.prices and self.prices[-1][0] <= price:
            del self.prices[-1]
            
        if self.prices:
            result -= self.prices[-1][1]
            
        self.prices.append([price, self.count])

        return result

C#

public class StockSpanner {
    List<(int price, int days)> prices;

    public StockSpanner() {
        prices = new List<(int price, int days)>();
    }
    
    public int Next(int price) {
        int result = 1;
        int i = prices.Count - 1;        
        while(i >= 0 && prices[i].price <= price)
            {
            result += prices[i].days;
            i -= 1;
            }
        prices.RemoveRange(i+1, prices.Count-i-1);
        prices.Add((price, result));
        return result;

} }