新高跨度(连续低价天数)
Span of Higher Highs
开始编码每天收盘后,量化研究员要给监控面板更新一列叫"新高跨度"的指标:对第 i 个交易日,往回数它连续打败了多少个收盘价——也就是从第 i 天起向左走,找到最长的一段连续日子,使得这一段里每一天的收盘价都严格低于 prices[i],再加上当天本身。这串数列在量化语境里有几个常见用途:判断当前价格相对短期历史的相对强弱、为突破策略生成入场信号、给「N 日新高」类因子做基础统计。当一只股票从盘整突破时,对应日的 span 会突然从个位数跳到几十甚至上百,是一个非常直观的形态指标。
请实现 solution(prices: list[float]) -> list[int]。prices 是一段按时间顺序排列的收盘价序列。返回一个等长的 list[int]:spans[i] 等于 1 + (从第 i-1 天向左数,与 prices[i] 形成严格下降阻挡前的连续天数)。换言之,spans[i] 是最大的 k,使得 prices[i-1], prices[i-2], ..., prices[i-k+1] 全部严格小于 prices[i](k 至少为 1,对应只有当天本身)。prices 为空时返回 []。
举例:solution([7.0, 5.0, 6.5, 6.5, 8.0, 8.5, 9.0]) 应返回 [1, 1, 2, 1, 5, 6, 7]。第 0 天没有左邻,跨度永远是 1;第 1 天的左邻是 7.0,并不严格低于 5.0,跨度还是 1;第 2 天的左邻 5.0 严格小于 6.5,再前面 7.0 不严格小于 6.5,跨度为 2;第 3 天的左邻 6.5 等于自己(不算严格低),跨度为 1;从第 4 天的 8.0 起价格突破前期所有阻挡,跨度一路扩展到第 6 天的 7(整段历史都被打败)。这条样本里第 3 天的「平价不计入」是最容易栽跟头的一处边界。
朴素做法对每个 i 都向左线性扫一遍,最坏 O(n²);在 n = 10⁵ 的规模下严格递增行情会跑成约 5 × 10⁹ 次比较,超时。正确做法是单调栈:维护一个索引栈,使得栈中索引对应的价格严格递减(更老的高价压在更下面)。处理第 i 天时把栈顶价格严格小于 prices[i] 的索引一口气弹光(这些天都被今天跨过去了),剩下的栈顶——如果存在——就是左侧最近的、价格 ≥ 今天的"阻挡日",跨度即为 i - 阻挡日索引;若栈被弹空,说明前面所有日子都比今天低,跨度就是 i + 1。最后把 i 自己压回栈。每个索引整个过程最多入栈、出栈各一次,摊还成本 O(1),总复杂度 O(n)。
约束条件
- 0 ≤ len(prices) ≤ 100000
- 每个 prices[i] 是一个 float 或 int,取值范围 [0.01, 1e6]
- 返回 list[int],长度严格等于 len(prices);若 prices 为空,返回空列表
- spans[i] 至少为 1(包含当天本身),spans[i] ≤ i + 1
- 「严格低于」按 `<` 判断:等价位**不**计入新高跨度
- 时间复杂度必须是 O(n) 摊还;O(n²) 在大用例下会超时
样例
Case 1 · example from statement (mixed with a tied price)
输入: [[7,5,6.5,6.5,8,8.5,9]]
期望: [1,1,2,1,5,6,7]
第 0 天没有左邻,跨度恒为 1。第 1 天的左邻 7.0 不严格小于 5.0,跨度仍是 1。第 2 天 6.5 看到左邻 5.0 严格更低(计 1 天)、再前面 7.0 不严格小于 6.5(停),跨度 2。第 3 天的左邻 6.5 等于自己,**不算**严格更低,跨度 1(这是平价边界)。第 4 天 8.0 一举打败前面所有 4 天 + 当天 = 5。第 5 天 8.5 把第 4 天也跨过去,跨度 6。第 6 天 9.0 把前面整段历史都打败,跨度 7。
Case 2 · strictly increasing rally (each day extends the run)
输入: [[1,2,3,4,5]]
期望: [1,2,3,4,5]
严格递增的多头行情下,每天都比之前所有天严格更高,跨度递增 1, 2, 3, 4, 5。这是最容易让朴素 O(n²) 解法暴露超时的形态——10⁵ 长度的严格递增序列会让朴素解跑出 ~5×10⁹ 次比较。
Case 3 · all prices equal (ties never extend the run)
输入: [[3.5,3.5,3.5,3.5]]
期望: [1,1,1,1]
等价位**不**算严格更低,所以每一天的跨度都被自己的左邻立即截断,全部为 1。把弹栈条件写成 `<=`(而不是 `<`)就会在这条用例上吐出 [1, 2, 3, 4],是这道题最常见的边界 bug。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · example from statement (mixed with a tied price)
输入: [[7,5,6.5,6.5,8,8.5,9]]
期望: [1,1,2,1,5,6,7]
第 0 天没有左邻,跨度恒为 1。第 1 天的左邻 7.0 不严格小于 5.0,跨度仍是 1。第 2 天 6.5 看到左邻 5.0 严格更低(计 1 天)、再前面 7.0 不严格小于 6.5(停),跨度 2。第 3 天的左邻 6.5 等于自己,**不算**严格更低,跨度 1(这是平价边界)。第 4 天 8.0 一举打败前面所有 4 天 + 当天 = 5。第 5 天 8.5 把第 4 天也跨过去,跨度 6。第 6 天 9.0 把前面整段历史都打败,跨度 7。
Case 2 · strictly increasing rally (each day extends the run)
输入: [[1,2,3,4,5]]
期望: [1,2,3,4,5]
严格递增的多头行情下,每天都比之前所有天严格更高,跨度递增 1, 2, 3, 4, 5。这是最容易让朴素 O(n²) 解法暴露超时的形态——10⁵ 长度的严格递增序列会让朴素解跑出 ~5×10⁹ 次比较。
Case 3 · all prices equal (ties never extend the run)
输入: [[3.5,3.5,3.5,3.5]]
期望: [1,1,1,1]
等价位**不**算严格更低,所以每一天的跨度都被自己的左邻立即截断,全部为 1。把弹栈条件写成 `<=`(而不是 `<`)就会在这条用例上吐出 [1, 2, 3, 4],是这道题最常见的边界 bug。