单调队列
给定一个长度为 n 的数组，需要输出每连续 k 个数（A[i, i+k-1]）中的最大值，可以在 O(n) 时间内做完吗？
一个思路就是动态地维护一个队列，在任何时刻 i 都满足
- 队列中的元素来自 A[i, i+k-1]
- A[s] 在队列中，当且仅当 A(s, i+k-1] 中的元素都小于 A[s]。特别地，A[i+k-1] 一定在队尾。
不难看出，“对头”或队列的最左侧元素就是 A[i, i+k-1] 的最大值。
每次增加 i，仅需：
- 从原队列的队尾开始逐个将不大于 A[i+k] 的元素弹出，然后让 A[i+k] 进队尾
- 检查对头的元素是否是 A[i]，如果是，将其弹出
每个元素最多进队、出队一次，因此算法是 O(N) 的。
滑动窗口
滑动窗口算法有诸多类型，如定长窗口、求最短窗口、求最长窗口等等。
用双指针 lp, rp 来把当前窗口定义为 A[lp, rp)，这样，移动左端和右端的操作就都很简单：
add A[rp] to window
rp = rp + 1
remove A[lp] from window
lp = lp + 1定长窗口
给定一个长度为 n 的数组，需要输出每连续 k 个数（A[i, i+k-1]）中第 x 小的数，复杂度可以多小？相关的例题：Leetcode 2653。
一个思路是，维护两棵平衡搜索树来存储窗口中的数，第一棵树大小为 x，第二棵树大小为 k-x，保证任何时刻第一棵树中的元素都小于第二棵树。这样，第一棵树的最大值就是窗口中第 x 小的数了。
每次移动窗口，需要删除一个元素，增加一个元素：
- 如果删除的元素在第一棵树中，增加的元素小于第二棵树的最小元素，则把增加的元素插入第一棵树。对称的情况同理。
- 如果删除的元素在第一棵树中，增加的元素大于第二棵树中最小的元素，则把第二棵树最小的元素转移到第一棵树中，在第二棵树中插入增加的元素即可。对称的情况同理。
这样做，需要 O( n (log(x)+log(k-x)) ) 的复杂度。使用堆（优先级队列）并不会减少其复杂度，尽管可能提升其实际性能。
如果使用全序向量的接口，那么这个问题就直接解决了：每次移动窗口增加一个、删除一个元素（各用时 O(k^{1/3})），然后读取第 k 小的数用时 O(1)，共用时 O(n k^{1/3})。
求最大窗口
如果一个窗口满足条件，则其所有子窗口都满足条件。特别地，长度为1的窗口都满足条件。
# Must be able to add any element when window is empty
lp, rp = 0, 0
while rp < len(A)
while cannot add A[rp] to window
remove A[lp] from window
lp = lp + 1
add A[rp] to window
rp = rp + 1
A[lp, rp) is a new valid window例：无重复字符 / 每个字符最多出现 k次 的最长子串
求最小窗口
如果一个窗口满足条件，则包含该窗口的任何窗口都满足条件。特别地，空窗口不满足条件。求最小窗口。
# Empty window (lp == rp) must not satisfy condition
lp, rp = 0, 0
while True:
while rp < len(A) and condition is not satisfied
add A[rp] to window
rp = rp + 1
if condition is not satisfied
break # we reached the end
while lp < rp and condition is satisfied
A[lp, rp) is a new valid window
remove A[lp] from window
lp = lp + 1例：Flowerpot（洛谷 P2698）给定一系列平面上的点 (x,y)，求最短的 x 区间使得该区间上的点 y 坐标极差不小于 D
Leave a Reply