0901. Online Stock Span¶
题目信息¶
- 题号:
0901
- 难度:
Medium
- 主题:
设计题、在线查询、连续历史区间
- 原题:
- 重点:
StockSpanner在多次调用之间保存历史价格;每次next的跨度包含当天,并只向前延伸到连续且价格不高于当天价格的日期
题目重述¶
实现 StockSpanner 类。对象创建后会按日期顺序多次调用 next(price),其中 price 是当天股票价格;每次调用都要把当天价格加入对象的历史状态。
next(price) 返回当天价格的跨度:从今天开始向前数,连续多少天的价格都小于或等于 price。一旦遇到更早且价格严格大于 price 的日期,跨度便在其后停止,因此返回值至少为 1。
1 <= price <= 10^5,对同一对象调用 next 的总次数不超过 10^4。
自建示例¶
价格回升但没有超过最早高点:
输入:
["StockSpanner","next","next","next","next","next"]
[[],[50],[40],[45],[35],[48]]
输出:[null,1,1,2,1,4]
解释:最后价格 48 连续覆盖当天以及此前的 35、45、40,共 4 天;再向前的 50 大于 48,因此跨度停止。
连续出现相同价格:
输入:
["StockSpanner","next","next","next"]
[[],[30],[30],[30]]
输出:[null,1,2,3]
解释:相等价格满足“不高于当天价格”。三个 30 依次加入后,跨度分别覆盖 1、2、3 天。