← 返回编程题库
coding-running-min-max-deque简单免费版2000ms未尝试

数据流的累积最小最大值

Running Min and Max of a Stream

开始编码

某高频监控盯着单 tick 的标量——价格、价差、深度失衡——每个 tick 都要汇报到目前为止观察到的累积最小值与最大值。和滚动窗口的统计不同,这里的「窗口」是单调增长的:从盘口开盘那一刻起,每个 tick 都会计入累积低点和累积高点,直到收盘。给定按时间排序的逐 tick 序列 values,返回逐事件的累积 (min, max) 配对,每个都是 2 元素列表。

请实现 solution(values: list[float]) -> list[list[float]]。输出长度等于 len(values),第 k 个输出(0 索引)是 [min(values[: k+1]), max(values[: k+1])]values 为空时返回 []

示例solution([3.0, 1.0, 4.0, 1.0, 5.0, 9.0, 2.0, 6.0]) 返回 [[3,3], [1,3], [1,4], [1,4], [1,5], [1,9], [1,9], [1,9]]——累积最小值在第 1 步从 3 降到 1 之后不再变;累积最大值依次爬到 4、5、9 之后稳定。solution([42.0]) 返回 [[42.0, 42.0]]——只有一个值时累积最小等于累积最大等于该值。solution([1.0, 2.0, 3.0, 4.0, 5.0]) 返回 [[1,1], [1,2], [1,3], [1,4], [1,5]]——严格递增流的累积最大值一直变大,累积最小值冻结在 values[0]

正确的数据结构是两个标量累加器,而不是双端队列。处理完空输入后用 current_min = current_max = values[0] 初始化,之后对每个 vcurrent_min = min(current_min, v)current_max = max(current_max, v),并把 [current_min, current_max] 追加到输出。由于累积流不淘汰任何元素,current_min 单调不增、current_max 单调不减,因此每步是 O(1)、总耗时是 O(N)。在这题里上堆或单调队列是「类别错误」——那些结构是为「元素会离开窗口、需要找下一个最优幸存者」准备的,累积统计根本没有这个找回问题。

实际背景:这是每个 tape 显示、每个突破检测告警、每个「创盘中新高/新低」通知背后的逐 tick session-high / session-low 原语,所有交易所或聚合器发布的每只标的都会跑这一份。每 tick 的工作量被刻意压到极小:min 一次比较加赋值,max 一次比较加赋值,append 一次。本题与 coding-sliding-window-max-quote 故意做对照,要把这条规则刻进肌肉记忆:有没有淘汰决定数据结构。没有淘汰 → 标量;定长窗口带淘汰 → 单调双端队列。

约束条件

  • 0 ≤ len(values) ≤ 100000
  • -1e9 ≤ values[i] ≤ 1e9(按 `float` 处理)
  • 输出长度必须等于 len(values);每项是一个 2 元素列表 `[min, max]`
  • 浮点比较使用 rel_tol=1e-9, abs_tol=1e-12

样例

Case 1 · typical mixed sequence — cumulative min and max evolve

输入: [[3,1,4,1,5,9,2,6]]

期望: [[3,3],[1,3],[1,4],[1,4],[1,5],[1,9],[1,9],[1,9]]

这是一条典型的混合序列。累积最小值在 i=1 时从 3 降到 1,此后不再变化;累积最大值在 i=2 时从 3 升到 4,在 i=4 升到 5,在 i=5 升到 9,之后不再增加。这验证了两个标量累加器独立更新的语义。

Case 2 · single value — min equals max equals the value

输入: [[42]]

期望: [[42,42]]

只有一个元素时,累积最小与最大都是它本身,输出为单一的 [42.0, 42.0]。

Case 3 · monotone increasing — max keeps growing, min frozen

输入: [[1,2,3,4,5]]

期望: [[1,1],[1,2],[1,3],[1,4],[1,5]]

单调递增:首个元素 1.0 始终是最小值;最大值随每步递增。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · typical mixed sequence — cumulative min and max evolve

输入: [[3,1,4,1,5,9,2,6]]

期望: [[3,3],[1,3],[1,4],[1,4],[1,5],[1,9],[1,9],[1,9]]

这是一条典型的混合序列。累积最小值在 i=1 时从 3 降到 1,此后不再变化;累积最大值在 i=2 时从 3 升到 4,在 i=4 升到 5,在 i=5 升到 9,之后不再增加。这验证了两个标量累加器独立更新的语义。

Case 2 · single value — min equals max equals the value

输入: [[42]]

期望: [[42,42]]

只有一个元素时,累积最小与最大都是它本身,输出为单一的 [42.0, 42.0]。

Case 3 · monotone increasing — max keeps growing, min frozen

输入: [[1,2,3,4,5]]

期望: [[1,1],[1,2],[1,3],[1,4],[1,5]]

单调递增:首个元素 1.0 始终是最小值;最大值随每步递增。