每日一题 901. 股票价格跨度（中等，单调栈）

理解题目，对于第 i 天，要求的是前 i - 1 天所满足条件的跨度

思路：

1. 暴力搜索的方式是，对于每一个第 i 天都遍历搜索 i - 1， i - 2，…，直到第 j 天大于当前价格
2. 优化，考虑哪里进行了重复搜索或者说第 i 天的跨度计算后是否可以用于后面某一天的跨度计算
3. 显然，如果第 j 天的跨度是 n（j < i），那么当对于第 i 天遍历搜索到第 j 天时，如果第 i 天的价格大于等于第 j 天，那么第 i 天的跨度可以直接加上 n，这样可以省去 n 次的重复判断，下一个判断就从 j - n 天开始

代码单调栈实现：

class StockSpanner:

    def __init__(self):
        self.l = [[1000000, 0]]

    def next(self, price: int) -> int:
        if price < self.l[-1][0]:
            self.l.append([price, 1])
            return 1
        
        ans = 1
        while price >= self.l[-1][0]:
            ans += self.l[-1][1]
            self.l.pop()
        
        self.l.append([price, ans])
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18