在线股价跨度
Online Stock Span
开始编码实时行情系统持续推送一支股票的最新成交价。每打印一个价格,研究台希望看到这一笔的「股价跨度」——也就是从今天往前数,有多少连续天的价格小于或等于今日价(含今日本身)。这是 LeetCode 901 的经典题,也是 microstructure 研究里常用的 streak counter:当前报价相对最近的历史"压制"了多久?跨度在切换行情(regime change)时会突然跳高,平静期则贴着低位——非常便宜的特征,可以直接喂给突破检测器或「连续不低于」类指标。
请实现 solution(prices: list[float]) -> list[int]。prices 按时间升序给出收盘价流。对每个下标 i,返回 spans[i] = 最大的 k ≥ 1,使得 prices[i-k+1], prices[i-k+2], ..., prices[i] 全部小于或等于 prices[i]。等价地说,从 i 向左数,统计连续多少天的价格 ≤ 今日价(含今日)。prices 为空时返回 []。
示例:solution([100.0, 80.0, 60.0, 70.0, 60.0, 75.0, 85.0]) 应返回 [1, 1, 1, 2, 1, 4, 6]。Day 0 单独算 1;Day 1(80.0)小于左边的 100.0,跨度 1;Day 3(70.0)能吃掉左边的 60.0(≤ 70.0),但被 80.0 挡住,跨度 2;Day 5(75.0)一口吃掉 60.0、70.0、60.0(全都 ≤ 75.0),被 80.0 挡住,跨度 4;Day 6(85.0)则把 75.0 那一整段连同 80.0、60.0 全吃光,一直追溯到 100.0 之前,跨度 6。最容易出错的子例是 solution([5.0, 5.0, 5.0, 5.0, 5.0]) → [1, 2, 3, 4, 5]:题面用 ≤ 而不是 <,所以相等也要计入。
朴素 O(n²) 重扫在 n = 10⁵ 的长横盘或上行序列上会超时。正解是 (price, span) 对的单调递减栈:栈中价格自底向上严格递减,所以任何栈顶 price ≤ 当日价的对都已被当日「传递性吞并」,可以直接把它的 span 折叠进当日。从左到右扫一遍,累加 span = 1 + 所有弹出 span 之和,再压入 (prices[i], span)。每个下标至多压栈一次、弹栈一次,整体摊还 O(n) 时间、O(n) 空间。
约束条件
- 0 ≤ len(prices) ≤ 100000
- 0 ≤ prices[i] ≤ 1e6
- 返回长度严格等于 len(prices) 的 list[int];空输入返回空列表
- spans[i] ∈ [1, i + 1](包含当日本身,至多到序列起点)
- 比较用 `<=`:相等的价格**计入**跨度(不是严格 `<`)
- 时间复杂度需为摊还 O(n);O(n²) 在长横盘或上行序列上会 TLE
样例
Case 1 · classic LC901 example
输入: [[100,80,60,70,60,75,85]]
期望: [1,1,1,2,1,4,6]
LeetCode 901 的经典示例。第 5 天(75.0)向左吃掉 60.0、70.0、60.0 三天,加上自身共 4;第 6 天(85.0)向左吃掉 75.0 那段(span=4)以及 80.0、60.0,加上自身共 6。
Case 2 · all equal — ties count toward span
输入: [[5,5,5,5,5]]
期望: [1,2,3,4,5]
题目用「≤」而非「<」:相等的价格也计入跨度。所以等价序列每一天的跨度都比前一天加 1。这是「≤」与「<」边界最容易出错的地方。
Case 3 · strictly decreasing — every span is 1
输入: [[7,6,5,4,3,2,1]]
期望: [1,1,1,1,1,1,1]
价格单调下降:每一天都比前一天严格更低,没有任何前一天 ≤ 当日,所以跨度恒为 1。栈始终保持单调递减且不会被弹出。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · classic LC901 example
输入: [[100,80,60,70,60,75,85]]
期望: [1,1,1,2,1,4,6]
LeetCode 901 的经典示例。第 5 天(75.0)向左吃掉 60.0、70.0、60.0 三天,加上自身共 4;第 6 天(85.0)向左吃掉 75.0 那段(span=4)以及 80.0、60.0,加上自身共 6。
Case 2 · all equal — ties count toward span
输入: [[5,5,5,5,5]]
期望: [1,2,3,4,5]
题目用「≤」而非「<」:相等的价格也计入跨度。所以等价序列每一天的跨度都比前一天加 1。这是「≤」与「<」边界最容易出错的地方。
Case 3 · strictly decreasing — every span is 1
输入: [[7,6,5,4,3,2,1]]
期望: [1,1,1,1,1,1,1]
价格单调下降:每一天都比前一天严格更低,没有任何前一天 ≤ 当日,所以跨度恒为 1。栈始终保持单调递减且不会被弹出。