假設測量值逐個到來,每收到一個值,都要找出最近 個值的最小值。對長度為 的序列,若每個視窗都重新檢查全部 項,就需要 次比較。單調雙端佇列可以用總共 的工作,回答這一批特定的區間查詢。
加速的關鍵,是記住哪些舊值仍有機會影響答案。有些候選離開視窗而到期;另一些候選則因為有較後到來、數值不更大的觀察值,而且後者至少能保留同樣長時間,而變得永久不再需要。這是兩種不同的刪除理由,正確實作必須同時處理。
先說清楚要回答哪些查詢
定義 12.1.1
(固定寬度視窗與最小值的見證下標)
設 的值具有一致的全序,並選整數 。對每個右端點 ,完整視窗為
我們同時回傳 和一個取得它的下標。若多個下標都取得最小值,預設規則回傳最晚的一個;稍後也會給出回傳最早下標的版本。
雙端佇列容許在兩端加入和刪去項目。我們儲存的是下標,而不只是數值。下標讓我們知道哪些候選已離開視窗,也能精確說明如何處理重複值。每一步的隊首是最舊的保留候選,隊尾則是最新的。
查詢的次序是問題的一部分:兩個端點每次都向前移一格。為這種視窗而設計的結構,並不會自動支援以任意次序提出的任意區間。浮點數 NaN 等不遵守假設中全序比較的值,不在本節的使用條件內。
為甚麼較後且不更大的值會令舊候選不再需要
引理 12.1.2
(支配引理)
設 且 。每個右端點 而且含 的定寬視窗,也含 ,並且 。因此對任何這類視窗, 都不是求最小值所必需的;在取最晚見證的規則下,它也從不是首選的見證。
證明透視
支配關係保留所有將來可能需要舊下標的視窗
假設 且 。考慮在 到來之後產生的視窗,其右端點為 。若視窗包含 ,則
所以它也包含 。較後的值不更大,而且比 更遲到期。因此,對任何這樣的未來視窗,要取得最小值都不再必須依靠 。
若兩值相等,而我們要最晚的最小值下標, 也是更合適的見證,所以可立即刪去 。若要求最早下標,相等本身不足以支持刪除 ;必須有嚴格更小的較後值才可以。
這個論證只討論新下標到來之後的未來視窗,不會改變之前已經需要輸出的答案。每個視窗都在處理其右端點時立即輸出,之後到來的值才可能刪去它當時的見證。
常見錯誤
(到下一個元素到達後才輸出答案)
取 、。結束於 的視窗是 ,最小值為下標 0 的 。若要等到處理完下標 2 才讀取它的答案,下標 0 已到期,新值 又刪去了下標 1,於是隊首是下標 2,報告的值為 ,而它並不在該視窗內。應在處理完 之後立即讀取隊首。
維持遞增下標與遞增數值
要回傳最晚的最小值下標,對每個新下標 按以下次序處理:
- 刪去小於新左端點 的隊首下標;它們已到期。
- 若隊尾下標 滿足 ,就反覆刪去它;新下標支配這些舊候選。
- 把 加到隊尾。
- 當 時,輸出隊首下標及其數值。
加入後,保留的下標由隊首至隊尾嚴格遞增,因為新下標比之前所有下標都大。它們的數值也嚴格遞增:第二步刪去所有不小於新值的隊尾,加入前剩下的最後一個值必較小。
定理 12.1.3
(單調雙端佇列的正確性)
採用取最晚最小值的規則時,在每個右端點 到達之後,雙端佇列的隊首就是視窗 中達到 的最晚下標。
證明透視
每個仍在視窗內的觀察值都有保留的代表
每次加入後,另維持以下不變量:對每個有效下標 ,都存在一個保留的下標 ,使
一個下標可以代表自己。若某個隊尾候選被新值刪去,新下標會支配該舊候選,也會藉兩個不等式的傳遞性,支配它原先代表的所有下標。新下標本身亦由自己代表。
若一個隊首候選到期,它不可能仍代表某個有效觀察值:被它代表的下標都不會比它更晚,所以也一定已到期。因此,到期刪除不會破壞對仍有效觀察值的覆蓋。
隊首是保留候選中數值最小的一個。所有保留下標本身都有效,而每個其他有效數值都有一個不更大的保留代表,所以隊首值恰好就是目前視窗的最小值。
這個最小值證明與平手規則之間,還有一個小分別。若要求最晚下標,較後的相同值到來時,較早的相同候選不會留下,因此目前最小值的最晚下標會保留。若要求最早下標,就保留相同值,讓候選數值非遞減,而不是嚴格遞增;第一個尚未到期的相同最小值,便是視窗內最早的一個。
分開追蹤相等、支配與輸出
例題 12.1.4
(最小值不變時,重複值仍會改變見證下標)
取 ,寬度 。表格採用預設規則:隊尾值大於或等於新值就刪去。佇列項目以「下標:數值」表示。
| 到來下標 | 數值 | 加入後的雙端佇列 | 完整視窗答案(下標,數值) |
|---|---|---|---|
| 尚未形成完整視窗 | |||
| 尚未形成完整視窗 | |||
在下標 2,新值與下標 1 的值相等,所以取代這個較舊候選。在下標 4,數值一刪去兩個較大的隊尾候選。在下標 6,它先刪去數值三,再取代下標 4 的相同舊最小值。
輸出的最小值為 ,相應的最晚下標為 。若改為保留相同值,同一批最小值的最早下標則為 。
例題 12.1.5
(嚴格遞減的輸入從不需要到期)
取 、。 時佇列為 。 時,隊尾值 被刪去,得 。 時,隊尾值 被刪去,得 ,第一個答案是下標 2、值 3。 時,隊首下標 2 不小於左端點 ,沒有東西到期;隊尾值 被刪去,得 ,答案是下標 3、值 2。 時情況相同,得 ,答案是下標 4、值 1。每次刪除都是由支配引起,佇列從不含超過一個下標,輸出為 。
例題 12.1.6
(寬度為 1 與 n 的極端情況)
取 。 時,每次到達 先使隊首下標 到期,再加入 ,所以答案是 :每個元素自成一個視窗。 時只有一個視窗。 時佇列為 ; 時,隊尾值 被刪去,得 ; 時, 不成立,所以佇列為 ,唯一的答案是隊首:下標 1、值 1。
反例模式
數值單調本身不會刪去已到期的隊首
取 ,。處理下標 2 後,全部候選仍在:下標 的數值遞增。在下標 3,新視窗是 ,所以必須從隊首刪去下標 0。正確答案是下標 1 的數值二。
若實作只刪去被支配的隊尾,便會保留舊值一,回傳一個已不在查詢區間內的觀察值。下標有效性是獨立於數值單調性的另一個不變量。
下面的互動圖逐次重播每個數據到達,把每次移除標明為到期或支配,並在兩種平手規則下把輸出的見證與直接掃描比較。
過期與支配,移除候選的理由不同
逐事件重播資料到達,分清前端過期與後端支配,並比較最早/最晚最小值見證。一次到達可做很多工作,而成功雙端操作總數仍是線性。
已在最後事件。
事件 27/27: 輸出完整視窗答案; 到達索引 r: 6.
完整視窗: [4,6]; k=3.
柱標籤顯示值及原索引。虛線框表示目前有效前綴/視窗;粗柱邊表示保留候選,三角形表示正在到達的索引。F/B 表示此事件移除的索引。未來數值供學習查看,演算法只使用已到達資料。表格提供相同資訊。
| 原索引 | 值 | 在目前前綴/視窗內 | 保留候選 | 理由 |
|---|---|---|---|---|
| 0 | 4 | 否 | 否 | 無 |
| 1 | 2 | 否 | 否 | 無 |
| 2 | 2 | 否 | 否 | 無 |
| 3 | 5 | 否 | 否 | 無 |
| 4 | 1 | 是 | 否 | 無 |
| 5 | 3 | 是 | 否 | 無 |
| 6 | 1 | 是 | 是 | 無 |
雙端佇列索引和值:前 → 後
6:1
前端 · 後端
加入後不變式檢查
- 保留索引嚴格遞增
- 是
- 保留值嚴格遞增
- 是
- 全部保留索引有效
- 是
- 候選數不超過 k
- 是
- 每個有效索引都有同位置或較晚且值不大的代表
- 是
加入後的完整視窗候選: (6,1); 此視窗的直接掃描見證: (6,1).
目前候選的值及平手見證皆正確: 是.
加入檢查點可在下一個輸出事件前已有候選;已輸出答案表只包含選定事件之前實際輸出的答案。
有效索引的代表見證
| 原索引 | 值 | 保留代表 j≥i,且 a[j]≤a[i] |
|---|---|---|
| 4 | 1 | 6:1 |
| 5 | 3 | 6:1 |
| 6 | 1 | 6:1 |
| 視窗左端點 | 視窗右端點 | 最小值見證索引 | 最小值 | 值及指定見證皆相同 |
|---|---|---|---|---|
| 0 | 2 | 2 | 2 | 是 |
| 1 | 3 | 2 | 2 | 是 |
| 2 | 4 | 4 | 1 | 是 |
| 3 | 5 | 4 | 1 | 是 |
| 4 | 6 | 6 | 1 | 是 |
計算成功雙端操作: 13 = 7 + 0 + 6.
成功移除數 ≤ 加入數: 6 ≤ 7; 本次到達的成功操作數: 3.
理想雙端佇列的一次加入或成功前/後端移除各算一單位。迴圈檢查及輸出另有線性總工作,但不在此計數內。快照複製、參考掃描及繪圖是額外教學成本,不是執行時間基準。
完整紀錄:每次到達完成後的摘要
| 到達索引 r | 因過期移除的索引 | 因支配移除的索引 | 加入後佇列 | 已輸出(索引,值) | 本次到達的成功操作數 | 累計操作 |
|---|---|---|---|---|---|---|
| [] | [] | 0:4 | 尚未有完整視窗 | 1 | 1 | |
| [] | [0] | 1:2 | 尚未有完整視窗 | 2 | 3 | |
| [] | [1] | 2:2 | (2,2) | 2 | 5 | |
| [] | [] | 2:2, 3:5 | (2,2) | 1 | 6 | |
| [] | [3,2] | 4:1 | (4,1) | 3 | 9 | |
| [] | [] | 4:1, 5:3 | (4,1) | 1 | 10 | |
| [] | [5,4] | 6:1 | (6,1) | 3 | 13 |
完整處理事件紀錄
| 事件 | 動作 | 到達索引 r | 被移除索引 | 雙端佇列索引和值:前 → 後 | 成功雙端操作總數 |
|---|---|---|---|---|---|
| 尚未有資料到達 | 無 | 無 | [] | 0 | |
| 新值到達,開始處理 | 0 | 無 | [] | 0 | |
| 加入到達的索引 | 0 | 無 | [0] | 1 | |
| 保留候選,尚未有完整視窗 | 0 | 無 | [0] | 1 | |
| 新值到達,開始處理 | 1 | 無 | [0] | 1 | |
| 移除被支配後端索引 | 1 | 0 | [] | 2 | |
| 加入到達的索引 | 1 | 無 | [1] | 3 | |
| 保留候選,尚未有完整視窗 | 1 | 無 | [1] | 3 | |
| 新值到達,開始處理 | 2 | 無 | [1] | 3 | |
| 移除被支配後端索引 | 2 | 1 | [] | 4 | |
| 加入到達的索引 | 2 | 無 | [2] | 5 | |
| 輸出完整視窗答案 | 2 | 無 | [2] | 5 | |
| 新值到達,開始處理 | 3 | 無 | [2] | 5 | |
| 加入到達的索引 | 3 | 無 | [2,3] | 6 | |
| 輸出完整視窗答案 | 3 | 無 | [2,3] | 6 | |
| 新值到達,開始處理 | 4 | 無 | [2,3] | 6 | |
| 移除被支配後端索引 | 4 | 3 | [2] | 7 | |
| 移除被支配後端索引 | 4 | 2 | [] | 8 | |
| 加入到達的索引 | 4 | 無 | [4] | 9 | |
| 輸出完整視窗答案 | 4 | 無 | [4] | 9 | |
| 新值到達,開始處理 | 5 | 無 | [4] | 9 | |
| 加入到達的索引 | 5 | 無 | [4,5] | 10 | |
| 輸出完整視窗答案 | 5 | 無 | [4,5] | 10 | |
| 新值到達,開始處理 | 6 | 無 | [4,5] | 10 | |
| 移除被支配後端索引 | 6 | 5 | [4] | 11 | |
| 移除被支配後端索引 | 6 | 4 | [] | 12 | |
| 加入到達的索引 | 6 | 無 | [6] | 13 | |
| 輸出完整視窗答案 | 6 | 無 | [6] | 13 |
- 目前加入數
- 7
- 目前前端移除數
- 0
- 目前後端移除數
- 6
- 成功雙端操作總數
- 13
- 本次到達的成功操作數
- 3
- 完成到達後的全部不變式成立
- 是
- 加入後的完整視窗候選
- (6,1)
- 目前候選的值及平手見證皆正確
- 是
例題重複最小值; k=3; 最晚:移除後端值 ≥ 新值; 移除過期索引. 事件 27/27: 輸出完整視窗答案; 到達索引 r: 6; 被移除索引: 無; 雙端佇列索引和值:前 → 後: [6]; 成功雙端操作總數: 13; 完成到達後的全部不變式成立: 是; 加入後的完整視窗候選: (6,1).
為何丟掉的候選不再需要
雙端佇列儲存原索引,不只儲存值。過期移除低於移動左界的索引。另一種刪除在較晚 j 的值不大於較早候選 i 時發生:以後任何含 i 的視窗也含 j,因為 r−k+1≤i<j≤r。替代者較晚過期,且值不大。
最晚見證在相等時偏好新索引,所以移除大於等於新值的後端值,保留值嚴格遞增。最早見證只移除嚴格較大值,令相等候選按索引保留,數值不減。兩規則回傳相同最小值,但原索引可能不同。
加入後,每個有效 i 都有保留 j≥i,滿足 a[j]≤a[i]。新索引代表自己,並透過遞移替代被支配候選的全部見證。過期代表不可能仍代表有效的較早索引。配合保留索引有效及值單調,前端便是視窗最小值。清理中途並不是這種完成到達後的檢查點。
[4,2,2,5,1,3,1]、寬三的輸出值為 [2,2,1,1,1]。最晚索引是 [2,2,4,4,6],最早是 [1,1,4,4,4]。索引 2 到達時,只有最晚規則會用較晚的相等 2 取代舊候選;索引 6 對兩個 1 也有同樣區別。
每個索引加入一次,之後至多成功移除一次,原因為過期或支配。因此成功移除總數≤n,計算的雙端操作≤2n。這是攤銷總界限。[1,2,3,4,0]、k=4 的最後到達使索引 0 過期,移除三個後端候選,再加入自己:此到達算五次操作,整段則九次。
若在 [1,2,3,4]、k=3 略去過期,最後視窗 [1,3] 的前端仍為舊索引 0,錯報值 1 而不是 2。候選值遞增不能修復索引有效性。正確保留佇列空間為 O(k),儲存輸出和完整教學紀錄另佔空間。反向視窗、修改舊值或中間刪除需要另外分析;本圖參數改變時會重建新的完整紀錄。
相等最小值會令見證規則無關緊要嗎?
不會。第一個例題視窗的值同為 2,但最早索引 1 與最晚索引 2 是不同的承諾輸出。直接掃描核對須同時比較值與指定的原索引見證,不能只比較最小數字。
本圖研究有限整數例子的固定寬最小值。寬介於一與資料長度。例子、寬、平手及過期規則改變時,會重建完整紀錄並選最後事件;重播只檢查該紀錄。數值輸出及操作數皆精確。成功操作採用抽象常數成本雙端佇列模型,不是 JavaScript 快照陣列的成本。最大值、任意區間查詢、可修改歷史資料及 NaN 等非全序不在範圍。
一次昂貴更新可以與線性總工作量同時成立
定理 12.1.7
(總工作量為線性)
對長度為 、寬度為 的序列,整段執行中雙端佇列共執行 次操作與比較,所以全部 個視窗最小值的計算時間為 ,雙端佇列空間為 。
證明透視
把每次刪除計入該下標唯一一次加入的成本
每個下標恰好加入一次。之後它可能因到期從隊首刪去,也可能因被支配從隊尾刪去,但不會被刪兩次。因此,整段執行中成功刪除的總次數不超過 。
其餘迴圈檢查只為每次到來增加常數工作,輸出一個答案也只需常數工作。因此,全部 個最小值總共只需 次雙端佇列操作與比較。目前視窗最多有 個保留下標,所以雙端佇列佔 空間。
這是攤銷成本的結論,並不是單次到來的最壞成本為常數。先把遞增數值 放進寬度 的視窗。當零接著到來,下標 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,得到視窗 ,下標 0 到期並被刪去。若下一個查詢又回到 ,便再次需要數值一,但佇列已經沒有儲存它。
左端點只向前移,才支持永久到期刪除。一旦容許後退,同一刪除規則就不再足以回答查詢。這個不同的問題需要靜態區間查詢結構或其他方法。
固定寬度是充分條件,卻不是唯一可能:只要左右端點都向前移,同一套有效期論證也可支援變動寬度的視窗。關鍵是較早且被支配的值,不會在其較後替代者缺席時再次被需要,而到期值也不會重新有效。任意刪去中間觀察值、修改較早數值,或以任意次序處理區間,都改變了這些保證,必須另作分析。
練習與詳解
快速檢查
(1. 同時追蹤下標與數值)
對 及寬度三,列出最晚與最早的最小值下標。為甚麼第一個完整視窗在兩種規則下具有相同數值,但回傳下標不同?
解答 · 解答 1
最晚下標是 ,最早下標是 。兩者的最小值同為 。第一個完整視窗在下標 1、2 取得相同最小值;刪去相同隊尾候選會留下 2,保留相同候選則讓 1 留在隊首。
快速檢查
(2. 補完支配論證)
假設 且 。某個未來寬度 k 的視窗,其右端點 ,並包含 i。寫出證明它也包含 j 的不等式。較遲到期為甚麼重要?
解答 · 解答 2
包含關係給出 ,所以 在同一視窗內,且提供不大於 的值。在向前滑動下, 比 更晚,不可能先於 到期。因此,舊候選仍可能被需要時,其替代者不會已經消失。
快速檢查
(3. 找出缺少到期處理的錯誤)
某實作以寬度三處理 ,卻只刪去被支配的隊尾。它對最後視窗會回傳哪個錯誤答案?給出正確見證,以及所需下標檢查。
解答 · 解答 3
它把下標 0 留在隊首,錯誤回傳數值一。最後視窗是 ,正確見證是下標 1、數值二。應刪去小於 的隊首下標;等價地,刪去不大於 的下標。
快速檢查
(4. 主動選擇重複值規則)
哪一個隊尾比較會產生最早最小值:大於,還是大於或等於?這個版本的保留數值具有甚麼單調性?
解答 · 解答 4
應用嚴格大於。相同候選按下標次序保留,所以最早且尚未到期的相同最小值會在隊首。數值非遞減,容許相等;大於或等於的比較則令數值嚴格遞增,實作最晚見證規則。
快速檢查
(5. 分清楚總工作量與單次到來的成本)
給出一段寬度 k 的輸入前綴及下一個值,使一次加入刪去 k 減一個隊尾候選。這為甚麼不違反線性總成本?
解答 · 解答 5
先加入 ,再加入零。最舊候選到期,零刪去其餘 個隊尾候選,這次到來需要 工作。每個被刪下標都只加入過一次,也不會再被刪,因此整段執行仍只有線性多次雙端佇列操作。
快速檢查
(6. 找出返回舊視窗破壞的假設)
對 ,依次處理 、,然後再次查詢 。哪個已刪下標再次被需要?哪一個向前滑動假設失效?
解答 · 解答 6
左端點推進至 1 時刪去下標 0,但視窗返回 後,它的數值一正是最小值。永久到期刪除假設左端點永不後退。新查詢違反這個假設,所以目前單調雙端佇列的狀態不足以回答它。