滑窗最低价的窗内偏移:每段定长窗口内最低价相对左缘的位置
Sliding-Window Argmin Offset: Per-Window Position of the Minimum Price Relative to the Window Left Edge
开始编码实现 solution(prices: list[float], window: int) -> list[int]。给定一段长度为 N 的合成价格序列 prices 和一个固定窗口长度 window,对每个连续长度为 window 的子段——按右端点 t = window-1, window, ..., N-1 索引——返回该窗口内最小价的窗内偏移:相对窗口左缘 t-window+1 的 0-based 位置;当窗口内最小价在多个位置同时取得时,取最早出现的那一个(即偏移最小者)。输出长度为 N - window + 1 的整型列表。当 window > N 或 N == 0 或 window < 1 时返回空列表 []。
例:solution([3.0, 1.0, 4.0, 1.0, 5.0, 9.0, 2.0], 3) 返回 [1, 0, 1, 0, 2]。窗口 [3, 1, 4](左缘 0)最小价 1 在绝对下标 1,偏移 1;窗口 [1, 4, 1](左缘 1)最小价 1 同时出现在绝对下标 1 与 3,按"最早"规则取绝对下标 1,相对左缘的偏移为 0;窗口 [4, 1, 5](左缘 2)偏移 1;窗口 [1, 5, 9](左缘 3)最小价 1 在绝对下标 3,偏移 0;窗口 [5, 9, 2](左缘 4)最小价 2 在绝对下标 6,偏移 2。
需要明确的细节:返回的偏移是相对窗口左缘的 0-based 值,而不是绝对下标;同价时按"最早出现位置"决出窗内最小;输出按位置 精确 比较(整数比较,不带浮点容差);当 window 超过 N 或输入为空时直接返回空列表。
朴素的双层循环(外层枚举窗口右端点,内层在 window 长度上做线性扫描求 argmin)复杂度为 O(N·window),在 N、window 同时较大的隐藏用例上会超时。标准做法是单调双端队列:队列中存绝对下标,对应价格从队首到队尾严格递增,每个下标至多入队出队各一次,整体 O(N)。
实现细节由 stubs/stub.py 提供。
实践背景
执行台的辅助监控模块需要对一段定长价格窗口实时计算"窗内最低价的相对位置"——本身既是给委托引擎的诊断字段,也用作回测里"最佳进场 tick"的参考点。具体来说:研究侧把该偏移序列看作窗口节奏特征——偏移普遍贴近窗口左缘说明短期下行能量集中在窗口前段、后段更可能反弹,反之则提示低点延迟出现、需要进一步观察;执行侧则把它接到子段的成交模拟里,作为"如果窗口结束时回顾,理想下单位置在哪"的事后基准。同价取最早位置的规则与桌面对成交时序的偏好一致:相同价位上更早的报价在大多数撮合规则下排队靠前、可成交概率更高,因此"最早"位置在执行后视角更具代表性,也避免被尾部重复 print 的冗余成交干扰。在长 tape 上每个窗口都做一次线性 argmin 会让监控线程跟不上 tape 速率,工程上必须把单步成本压成均摊 O(1),单调双端队列是这一类滑窗极值结构的标准范式,写一遍后还可推广到窗内 max、窗内极值价差等同族指标。
约束条件
- 0 <= N <= 200000,其中 N 是 solution(prices, window) 的输入长度
- 1 <= window <= N;当 window > N 或 N == 0 或 window < 1 时返回空列表
- 每个 prices[i] 为 -1e9 到 1e9 之间的浮点数
- 输出长度为 N - window + 1,第 k 项是第 k 个窗口(右端点 t = window-1 + k)内最小价的窗内偏移(相对窗口左缘 t-window+1 的 0-based 偏移),同价取最早位置
- 输出按位置精确比对(exact 整数比较),不允许浮点容差
样例
Case 1 · statement-example: window=3 over 7-tick mixed series
输入: [[3,1,4,1,5,9,2],3]
期望: [1,0,1,0,2]
依次窗口 [3,1,4]、[1,4,1]、[4,1,5]、[1,5,9]、[5,9,2],最小价的窗内偏移分别为 1、0(同价取最早,绝对下标 1 在左缘 1 处偏移 0)、1、0、2。
Case 2 · visible: all equal prices, tie always at offset 0
输入: [[2,2,2,2],2]
期望: [0,0,0]
全部价格相同,每个长度为 2 的窗口最小都在窗口左缘,按最早出现位置规则偏移恒为 0。
Case 3 · visible: window equals N, min at front
输入: [[1,2,3,4,5],5]
期望: [0]
整段单调递增,唯一窗口的最小价在最前端,偏移为 0。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: window=3 over 7-tick mixed series
输入: [[3,1,4,1,5,9,2],3]
期望: [1,0,1,0,2]
依次窗口 [3,1,4]、[1,4,1]、[4,1,5]、[1,5,9]、[5,9,2],最小价的窗内偏移分别为 1、0(同价取最早,绝对下标 1 在左缘 1 处偏移 0)、1、0、2。
Case 2 · visible: all equal prices, tie always at offset 0
输入: [[2,2,2,2],2]
期望: [0,0,0]
全部价格相同,每个长度为 2 的窗口最小都在窗口左缘,按最早出现位置规则偏移恒为 0。
Case 3 · visible: window equals N, min at front
输入: [[1,2,3,4,5],5]
期望: [0]
整段单调递增,唯一窗口的最小价在最前端,偏移为 0。