0901. Online Stock Span

题目信息

题号:

0901

难度:

Medium

主题:

设计题、在线查询、连续历史区间

原题:

LeetCode 0901

重点:

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 天。