假设测量值依次到达,我们希望在每次到达后求出最近 个值的最小值。对于长度为 的序列,如果每个窗口都重新检查全部 个元素,总共需要 次比较。单调双端队列则能用 的总工作量回答所有这些特定的区间查询。
加速的关键是记住哪些旧值仍有可能影响答案。有些候选项因离开窗口而过期;另一些则因为后来的值不大于它,而且至少与它一样晚才离开窗口,从此不再需要。这是两种不同的删除原因,正确的实现必须分别处理。
明确要回答的查询
定义 12.1.1
(定长窗口与最小值的见证下标)
设 是具有一致全序的值,并选定整数 。对每个右端点 ,完整窗口及其最小值为
我们同时返回 和一个取到该值的下标。如果有多个下标取到最小值,默认返回最靠后的下标;之后还会介绍返回最靠前下标的变体。
双端队列允许在两端插入和删除。这里队列存储的是下标,而不只是值。下标让我们能判断候选项是否已经离开窗口,也能准确描述相等时的处理规则。任意时刻,队首是保留下来的最早下标,队尾是最晚下标。
查询的顺序也是问题的一部分:两个端点每次向前移动一个位置。为这类窗口设计的数据结构,并不自动适用于以任意顺序给出的任意区间。浮点数 NaN 等不满足所假设全序比较规则的值,不在这里讨论的输入范围内。
为什么后来的较小或相等值能取代旧值
引理 12.1.2
(支配引理)
设 且 。每个右端点 而且含 的定长窗口,也含 ,并且 。因此对任何这类窗口, 都不是求最小值所必需的;在取最晚见证的规则下,它也从不是首选的见证。
证明透视
支配关系保留了此后所有可能需要旧下标的窗口
假设 且 。考虑 到达之后产生的一个窗口,其右端点满足 。如果该窗口包含 ,那么
因此它也包含 。后一个值不大于前一个值,而且比 更晚过期。所以,对此后的任何这类窗口,取得最小值都不需要依靠 。
如果两值相等,而我们要的是最靠后的最小值下标,那么 也是更合适的见证下标,可以立即丢弃 。如果要求最靠前的下标,仅凭相等不能删除 ;只有后来出现的值严格更小时才能删除它。
这个论证针对新下标到达之后的窗口,不会改变更早窗口已经需要的答案。处理每个窗口的右端点时,我们就输出该窗口的答案,然后才处理可能删除其见证下标的后续元素。
常见错误
(到下一个元素到达后才输出答案)
取 、。结束于 的窗口是 ,最小值为下标 0 的 。若要等到处理完下标 2 才读取它的答案,下标 0 已过期,新值 又删去了下标 1,于是队首是下标 2,报告的值为 ,而它并不在该窗口内。应在处理完 之后立即读取队首。
维护递增的下标和递增的值
对于返回最靠后最小值下标的规则,按以下顺序处理每个新到达的下标 :
- 从队首删除小于新左端点 的下标;它们已经过期。
- 只要队尾下标 满足 ,就删除它。新下标支配这个旧下标。
- 将 加入队尾。
- 当 时,输出队首下标及其值。
插入之后,保留的下标从队首到队尾严格递增,因为每次新加入的下标都比之前的大。它们对应的值也严格递增:第二步删除所有大于或等于新值的队尾值,所以追加之前若队列非空,其最后一个值必定较小。
定理 12.1.3
(单调双端队列的正确性)
采用取最晚最小值的规则时,在每个右端点 到达之后,双端队列的队首就是窗口 中达到 的最晚下标。
证明透视
每个仍在窗口内的元素都有保留的代表
在每次插入后,使用以下附加不变量:对每个仍在窗口内的下标 ,存在保留的下标 满足
一个下标可以代表自身。当新的值使队尾一个保留下标被删除时,由两个不等式的传递性,新下标不仅支配被删去的候选项,也支配该候选项原先代表的所有下标。新下标还代表自身。
当队首候选项过期时,它不可能代表仍在窗口内的元素:它所代表的任何下标都不晚于它,因此也已经过期。故删除过期项仍能保持对窗口内元素的覆盖。
队首的值是所有保留候选值中的最小值。保留的下标本身都在窗口内,而窗口中任何其他值都有一个不大于它的保留下标作为代表。因此,队首值恰好是当前窗口的最小值。
最小值的证明和相等时的下标规则略有不同。若要最靠后的见证下标,较晚的相等值到达时,较早的相等候选项不会被保留。因此,当前最小值中最靠后的下标会留下来。若要最靠前的见证下标,则保留相等值,使队列中的值不下降,但不一定严格递增;此时最前面仍有效的相等最小值下标就是所求。
分别追踪相等、支配与输出
例题 12.1.4
(即使最小值不变,重复值也可能改变见证下标)
令 ,窗口宽度 。下表采用默认规则:当队尾值大于或等于新值时删除队尾。队列元素写作“下标:值”。
| 新到达的下标 | 值 | 插入后的队列 | 完整窗口的答案(下标,值) |
|---|---|---|---|
| 窗口尚未完整 | |||
| 窗口尚未完整 | |||
在下标 2 处,新值与下标 1 处的值相等,因此取代了较早的候选项。在下标 4 处,值 1 删除了队尾两个较大的候选项。在下标 6 处,新值先删除 3,再取代下标 4 处较早的相等最小值。
输出的最小值为 ,对应的最靠后见证下标为 。如果保留相等值,同一组最小值对应的最靠前下标则为 。
例题 12.1.5
(严格递减的输入从不需要过期)
取 、。 时队列为 。 时,队尾值 被删去,得 。 时,队尾值 被删去,得 ,第一个答案是下标 2、值 3。 时,队首下标 2 不小于左端点 ,没有东西过期;队尾值 被删去,得 ,答案是下标 3、值 2。 时情况相同,得 ,答案是下标 4、值 1。每次删除都是由支配引起,队列从不含超过一个下标,输出为 。
例题 12.1.6
(宽度为 1 与 n 的极端情况)
取 。 时,每次到达 先使队首下标 过期,再加入 ,所以答案是 :每个元素自成一个窗口。 时只有一个窗口。 时队列为 ; 时,队尾值 被删去,得 ; 时, 不成立,所以队列为 ,唯一的答案是队首:下标 1、值 1。
反例模式
值的单调性本身不能删除过期的队首
取 ,。处理完下标 2 后,所有候选项都保留:下标 对应的值递增。到下标 3 时,新窗口为 ,因此必须从队首删除下标 0。正确答案是下标 1 处的值 2。
如果实现只删除被支配的队尾值,就会保留旧值 1,并返回查询区间之外的元素。下标有效性与值的单调性是两个不同的不变量。
下面的互动图逐次重放每个数据到达,把每次移除标明为过期或支配,并在两种平局规则下把输出的见证与直接扫描比较。
单次更新可能昂贵,总工作量仍可为线性
定理 12.1.7
(总工作量为线性)
对长度为 、宽度为 的序列,整个运行中双端队列共执行 次操作与比较,所以全部 个窗口最小值的计算时间为 ,双端队列空间为 。
证明透视
把每次删除计入该下标唯一的一次插入
每个下标恰好被追加一次。之后,它要么因过期而从队首删除,要么因被支配而从队尾删除,但不可能被删除两次。因此,整个过程中的成功删除次数最多为 。
其余循环条件检查在每次元素到达时只增加常数工作量,输出一次答案也只需常数工作量。因此,求出全部 个最小值需要 次双端队列操作和比较。当前窗口中最多保留 个下标,所以队列使用 空间。
这是均摊意义下的结论,并不意味着每次到达的最坏代价都是常数。先向宽度为 的窗口依次插入递增值 。接着插入 0 时,下标 0 过期;新来的 0 会从队尾删除其余 个候选项。这一次更新需要 的工作量。但在整个过程中,被删除的候选项不能再次被计费。
队列本身使用 内存。若函数保存全部答案,还需要额外的 输出空间。下面的实现为了方便按下标访问,也将输入序列完整存储。在线实现可以改为在队列中存储“下标:值”对,并在答案产生时立即输出;这样无需保留完整输入,工作内存仍为 。
明确相等值规则的实现
函数接受一个非空有限输入序列和合法的整数窗口宽度。示例使用整数,所以比较是精确的。默认返回最靠后的最小值下标;设置 earliest=True 只会改变队尾值相等时的处理方式。
from collections import deque
def sliding_minima(values, width, earliest=False):
values = tuple(values)
if not 1 <= width <= len(values):
raise ValueError("width must lie between one and the sequence length")
candidates = deque()
answers = []
for right, value in enumerate(values):
left = right - width + 1
while candidates and candidates[0] < left:
candidates.popleft()
while candidates:
old_value = values[candidates[-1]]
dominated = old_value > value if earliest else old_value >= value
if not dominated:
break
candidates.pop()
candidates.append(right)
if left >= 0:
index = candidates[0]
answers.append((index, values[index]))
return answers
对于例题数据,sliding_minima([4,2,2,5,1,3,1], 3) 返回 [(2,2),(2,2),(4,1),(4,1),(6,1)]。设置 earliest=True 后返回 [(1,2),(1,2),(4,1),(4,1),(4,1)]。宽度为 1 时,每次返回刚到达的元素;宽度为 时,整个输入只产生一个答案。返回的下标是原序列下标,而不是相对于当前窗口的位置。
若要求最大值,反转支配比较即可:对于返回最靠后最大值下标的规则,队尾值不大于新值时删除队尾。下标过期的处理不变。证明中将值的顺序反过来即可,而关于存续时间的论证保持不变。
查询改变时,哪些删除仍然安全
反例模式
左边界向后移动时,丢弃的下标无法恢复
取递增值 。处理窗口 后,队列包含全部三个下标。将左边界移到 1,得到窗口 ;下标 0 过期并被丢弃。如果下一个查询又回到 ,就重新需要值 1,而队列已不再存储它。
左边界向前移动,才使永久删除过期项有依据。一旦允许向后移动,相同的删除规则就不再适用于这些查询。对于这一不同的问题,需要静态区间查询结构或其他方法。
定长窗口是充分条件,但并非严格必要:相同的存续时间推理也可以支持左右端点都向前移动的窗口。关键在于,被支配的旧值不会在其较晚的替代值不在窗口内时重新变得必要,且过期值不会再次进入活动窗口。任意删除中间元素、修改先前的值或以任意顺序处理区间,都会改变这些保证,需要另行分析。
练习与详解
快速检查
(1. 同时追踪下标和值)
对 和宽度为 3 的窗口,分别列出最靠后和最靠前的最小值下标。为什么第一个完整窗口在两种规则下的最小值相同,返回的下标却不同?
解答 · 解答 1
最靠后下标为 ,最靠前下标为 。两种情况下的最小值都是 。第一个完整窗口在下标 1 和 2 处有相等的最小值:删除相等的队尾候选项会保留 2;保留相等候选项则使 1 留在队首。
快速检查
(2. 补全支配关系的证明)
假设 且 。一个未来宽度为 的窗口,其右端点 ,并且包含 。写出证明该窗口也包含 的不等式。为什么较晚过期很重要?
解答 · 解答 2
由包含关系得到 ,所以 也位于同一窗口,并提供一个不大于 的值。由于 更晚,在窗口向前滑动时它不可能比 先过期。因此,当较早的候选项仍然需要时,替代项不会已经消失。
快速检查
(3. 找出缺失的过期步骤)
某实现以宽度 3 处理 ,但只删除被支配的队尾候选项。它对最后一个窗口会给出什么错误答案?给出正确的见证下标和所需的下标检查。
解答 · 解答 3
它会将下标 0 保留在队首,错误地返回值 1。最后一个窗口为 ,正确的见证下标是 1,对应值为 2。应删除小于 的队首下标;等价地,删除不大于 的下标。
快速检查
(4. 主动选择重复值规则)
要得到最靠前的最小值下标,队尾比较应使用“大于”还是“大于或等于”?这一版本中,保留的值具有什么单调性?
解答 · 解答 4
使用严格大于。相等候选项按下标顺序保留,所以仍有效的最靠前相等最小值位于队首。值是非递减的,允许相等。使用大于或等于则使值严格递增,并实现最靠后的见证下标规则。
快速检查
(5. 区分总工作量与单次到达的代价)
给出一个宽度为 的输入前缀及下一个值,使一次插入删除 个队尾候选项。为什么这不与线性总工作量矛盾?
解答 · 解答 5
依次插入 ,然后插入 0。最早的候选项过期,0 删除其余 个队尾候选项,因此这次到达需要 的工作量。这些下标各自只被插入一次,也不可能再次被删除,所以整个过程仍然只有线性数量的队列操作。
快速检查
(6. 找出窗口返回时被破坏的假设)
对 ,先处理 ,再处理 ,然后再次查询 。哪个已丢弃的下标又被需要了?哪个向前滑动的假设失效了?
解答 · 解答 6
左边界前移到 1 时,下标 0 被删除;但窗口返回 时,其值 1 又是最小值。永久删除过期项依赖于左边界永不向后移动的假设。新查询违反了这一假设,所以当前单调双端队列的状态不足以回答它。