假設測量值逐個到來,每收到一個值,都要找出最近 個值的最小值。對長度為 的序列,若每個視窗都重新檢查全部 項,就需要 次比較。單調雙端佇列可以用總共 的工作,回答這一批特定的區間查詢。
加速的關鍵,是記住哪些舊值仍有機會影響答案。有些候選離開視窗而到期;另一些候選則因為有較後到來、數值不更大的觀察值,而且後者至少能保留同樣長時間,而變得永久不再需要。這是兩種不同的刪除理由,正確實作必須同時處理。
先說清楚要回答哪些查詢
定義 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 的數值二。
若實作只刪去被支配的隊尾,便會保留舊值一,回傳一個已不在查詢區間內的觀察值。下標有效性是獨立於數值單調性的另一個不變量。
下面的互動圖逐次重播每個數據到達,把每次移除標明為到期或支配,並在兩種平手規則下把輸出的見證與直接掃描比較。
一次昂貴更新可以與線性總工作量同時成立
定理 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,但視窗返回 後,它的數值一正是最小值。永久到期刪除假設左端點永不後退。新查詢違反這個假設,所以目前單調雙端佇列的狀態不足以回答它。