力扣 901. 股票价格跨度

思路

分别保存每日股价以及每日股票跨度，

对每日股价倒叙查找，判断查找的股价小于等于当日股价，则根据他的股票跨度进行倒退，再次判断直到查找的股价大于当日股价，

得到最终当日股价的跨度。

解法

class StockSpanner:

    def __init__(self):
        self.prices = []
        self.dp = []


    def next(self, price: int) -> int:
        cur, dp = len(self.prices) - 1, 1
        while cur > -1 and self.prices[cur] <= price:
            dp += self.dp[cur]
            cur -= self.dp[cur]
        self.prices.append(price)
        self.dp.append(dp)
        return self.dp[-1]