单序列扫描与边界
本节目标
在一次扫描中维护前缀最优、可达边界或下一层边界。
序列题常把“未来还有哪些选择”压缩为一个边界：历史最低价格、当前最远可达位置，或下一次跳跃能覆盖的最远位置。只要这个状态完整描述了前缀对后缀的影响，便不必枚举所有路径。
识别信号
- 每个位置的决策只依赖此前最优摘要，而非完整历史。
- 相邻元素的差值可以拆解总收益。
- 当前位置能够覆盖一个连续后缀区间，题目询问可达性或最少层数。
问题模型与核心不变量
扫描到位置 i 时，前缀最低价格是所有可能买入日的最佳摘要；最远可达边界是已扫描位置能到达的最大下标。最少跳数还需区分本层边界与下一层边界：扫描本层所有落点后才增加一次跳跃。
通用模板
初始化一个前缀最优或可达边界
从左到右扫描：
用当前位置更新答案或下一轮边界
若当前位置已超出可达边界：失败
若当前位置到达本层边界：进入下一层
模板变体
- 单次交易保留历史最低价格；每一天只尝试“今天卖出”。
- 无限交易将每段上涨拆为相邻正差值之和。
- 跳跃可达性只需一个最远边界；最少跳数还需把连续可达区间视作 BFS 的一层。
母题序列
- 买卖股票的最佳时机（必学）：前缀最低价与一次卖出的最大收益。
- 买卖股票的最佳时机 II（必学）：把每段上涨拆成正差值。
- 跳跃游戏（必学）：维护当前可达的最远位置。
- 跳跃游戏 II（必学）：把可达位置切成最少跳跃层。
常见误区
- 将单次交易的最低价逻辑直接套到无限交易，遗漏中间上涨段。
- 到达某个位置才更新边界，漏掉当前位置可提供的跳跃长度。
- 最少跳数在每次刷新最远边界时都加一，误把同一层的多个位置算成多跳。
- 忘记单元素序列已经在终点。
迁移方向
区间覆盖也维护“当前能接上的最远右端点”；字符串分段维护“当前片段的最远最后位置”。它们的状态不同，但都遵循“扫描前缀只保留影响后缀的边界”。