第 43 章　双指针与滑动窗口

配套例题：BISHI114 【模板】滑动窗口、BISHI115 可匹配子段计数、 BISHI116 【模板】双指针、BISHI117 小苯的 IDE 括号问题、 BISHI118 相差不超过 k 的最多数、BISHI119 小红的 01 子序列构造、BISHI120 ？？？ 来源：S3 day4《序列算法选讲》（阮行止）第 6–17 页「2-pointers」； day4 deque(更正).cpp

双指针是用「单调性」把 \(O(n^2)\) 的二重循环压成 \(O(n)\) 的技巧。 它的核心不是「两个变量」，而是这句话：

右端点右移时，左端点只会右移、绝不会左移。

有了这条单调性，两个指针各自最多走 \(n\) 步，总步数 \(\le 2n\)，所以是 \(O(n)\)—— 哪怕代码里有嵌套的 while。「有嵌套循环 ≠ 复杂度是平方」，这是双指针最反直觉的地方。

---

43.1　三种双指针

类型	指针走向	典型问题
同向双指针（尺取法）	都从左往右	最长/最短满足条件的子段
对撞指针	一左一右往中间	有序数组两数之和、回文判定、田忌赛马
快慢指针	同向不同速	链表找环 / 找中点

第三种见 31-链表，本章讲前两种。

---

43.2　同向双指针的通用框架

背下这个骨架，90% 的滑窗题都是往里填三行。

l = 0                              # 窗口左端，闭区间 [l, r]
best = 0
# state = ...                      # 窗口内的统计量：和 / 计数器 / 不同元素数 ...
for r in range(n):
    # 1) 把 a[r] 加入窗口，更新 state
    add(a[r])

    # 2) 只要窗口非法，就收缩左端。l 只增不减：r 变大后，更靠左的左端只会更非法
    while not ok(state):
        remove(a[l])
        l += 1

    # 3) 循环不变量：每轮结束时 [l, r] 合法，且 l 是使它合法的最小值
    best = max(best, r - l + 1)

# 均摊 O(n) 的理由：r 走 n 步，l 至多也走 n 步且从不回退，内层 while 的总执行次数 <= n。
# 所以「嵌套 while」并不意味着平方复杂度——前提是 add / remove 都是 O(1)

三条使用要点：

要点	说明
while 而不是 if	加入一个元素可能要弹掉多个
add / remove 必须 \(O(1)\)	否则总复杂度不是 \(O(n)\)
循环不变量	每轮结束时 [l, r] 都是合法的

求「最短」而不是「最长」时，收缩条件要反过来

l = 0
best = INF
for r in range(n):
    add(a[r])
    while ok(state):               # 只要还合法就继续缩，找最短
        best = min(best, r - l + 1)    # 在缩之前记录：此刻 [l, r] 还是合法的
        remove(a[l])
        l += 1                     # 缩到刚好破坏合法性为止，下一轮再靠 r 补回来

「最长」在 while 外统计，「最短」在 while 内统计。 这一条写反是滑窗题最高频的 WA。

什么时候双指针是错的

双指针成立的前提是单调性：

• 求最长：窗口合法 ⟹ 它的任意子区间也合法（合法性对收缩封闭）；
• 求最短：窗口非法 ⟹ 它的任意子区间也非法。

典型的反例是「子段和恰好为 \(k\)，但数组里有负数」——加入元素时和不再单调递增， 右端右移后左端可能需要回退。这类题必须改用前缀和 + 哈希表，见 42-前缀和与差分 §42.5。

数组元素	「和 \(\le k\) 的最长子段」
全为正	✅ 双指针 \(O(n)\)
含 0	✅ 仍然可以（和不减）
含负数	❌ 双指针失效，改用前缀和 + 单调队列 / 哈希

---

43.3　对撞指针

两个指针从两端往中间走，每一步至少排除一个候选，所以也是 \(O(n)\)。

# 有序数组里找和为 target 的一对
l, r = 0, n - 1                    # 一左一右，候选是所有满足 l < r 的下标对
while l < r:                       # 相遇即停：l == r 时只剩一个元素，配不成对
    s = a[l] + a[r]
    if s == target:
        break
    if s < target:
        l += 1                     # 和太小 -> a[l] 与更小的右端配只会更小，整列淘汰，只能增大左端
    else:
        r -= 1                     # 和太大 -> a[r] 与更大的左端配只会更大，整列淘汰，只能减小右端
# 每一步至少淘汰一行或一列候选，两个指针合计最多走 n 步，所以是 O(n)

对撞指针几乎总是要先排序，因为它靠的是「往左变小、往右变大」这个单调性。 田忌赛马式的贪心（最快的对最快的，跑不过就用最慢的去消耗）也是对撞指针的应用，见 47-贪心。

---

43.4　单调队列：滑动窗口最值

滑窗最值不能用前缀和（max 没有逆运算），也不必上线段树——单调队列是 \(O(n)\) 的最优解。

思想：队列里存下标，对应的值单调递减。若新元素比队尾大，队尾那些元素 「既比新元素小、又比新元素早过期」，永无出头之日，直接弹掉。

from collections import deque


def sliding_max(a, k):
    """长度为 k 的滑动窗口最大值，返回 n-k+1 个结果，O(n)。"""
    dq = deque()                    # 存下标，对应值单调递减，a[dq[0]] 是当前窗口最大值
    res = []
    for i, v in enumerate(a):
        # 队尾那些元素既比 v 小、又比 v 先过期，此后永远当不上最大值，可以永久丢弃
        while dq and a[dq[-1]] <= v:      # 队尾比新元素小 -> 永远轮不到它
            dq.pop()
        dq.append(i)                      # 入队后，队列里的值仍保持单调递减
        if dq[0] <= i - k:                # 窗口是 [i-k+1, i]，下标 <= i-k 的已经出界
            dq.popleft()
        if i >= k - 1:                    # 前 k-1 步窗口还没填满，不输出
            res.append(a[dq[0]])
    # 每个下标最多入队一次、出队一次，总操作 <= 2n，所以整体是均摊 O(n)
    return res

求最小值只需把 <= 改成 >=。四个必须记牢的细节：

细节	原因
队列里存下标不存值	判断过期要靠下标
弹队尾用 while 不用 if	一次可能弹掉多个
<= 还是 <	用 <= 弹掉等值元素，队列更短；用 < 也对但会留冗余
必须用 deque	list.pop(0) 是 \(O(n)\)，会退化成 \(O(n^2)\)

collections.deque 的两端操作是 \(O(1)\)，随机访问 dq[i] 是 \(O(n)\)。 单调队列只访问 dq[0] 和 dq[-1]，这两个是特化过的 \(O(1)\)，放心用。 见 33-队列与双端队列。

单调队列与单调栈的对照、以及它在 DP 优化里的用法，见 37-单调栈与单调队列 与 104-DP优化。

---

43.5　窗口内「状态」的四种维护方式

滑窗题的难点从来不是指针，而是如何 \(O(1)\) 地维护窗口状态。

要维护的量	数据结构	加入 / 删除
区间和	一个变量	s += x / s -= x
每个值出现次数	Counter / list 桶	cnt[x] += 1 / -= 1
不同元素个数	Counter + 计数器	计数从 0→1 时 distinct += 1
区间最值	单调队列	见 43.4

第三种的标准写法（这是「最多 \(k\) 种不同元素的最长子段」类题的核心）：

from collections import Counter

cnt = Counter()                    # 窗口内每个值的出现次数
distinct = 0                       # 窗口内不同值的个数
l = 0
for r in range(n):
    if cnt[a[r]] == 0:             # 计数由 0 变 1 的那一刻，才是「新增一种」
        distinct += 1              # 新出现的值
    cnt[a[r]] += 1
    while distinct > k:            # 种类超标，收缩左端直到合法
        cnt[a[l]] -= 1
        if cnt[a[l]] == 0:         # 计数由 1 变 0 的那一刻，才是「少了一种」
            distinct -= 1          # 这个值彻底离开窗口
        l += 1

---

43.6　例题

BISHI114　【模板】滑动窗口（简单）

\(n \le 2\times10^5\)，窗口大小 \(k\)，输出每个窗口的最大值。 题面见 BISHI114 原题（牛客）。

单调队列的裸模板：

import sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    a = list(map(int, data[2:2 + n]))

    dq = deque()                          # 存下标，对应值单调递减；队首即当前窗口最大值
    out = []
    ap = out.append
    for i in range(n):
        v = a[i]
        # 队尾元素比 v 小且比 v 先过期，永远没有出头之日，直接丢弃
        while dq and a[dq[-1]] <= v:      # 队尾比新元素小的都没用了
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                # 当前窗口是 [i-k+1, i]，下标 <= i-k 的已过期
            dq.popleft()
        if i >= k - 1:                    # 窗口首次填满是在 i == k-1，从这里开始输出
            ap(a[dq[0]])
    # 每个下标入队、出队各至多一次，总代价 O(n)
    sys.stdout.write(" ".join(map(str, out)) + "\n")


main()

• 样例 2（\(k=1\)）：每次新元素进来会把队尾全弹光，答案就是原数组，逻辑自洽。
• 样例 3（\(k=n\)）：只输出一个全局最大值，说明 i >= k-1 的判断不能写成 i >= k。
• 不要用 list 当队列：pop(0) 是 \(O(n)\)，\(2\times10^5\) 时直接退化。

若题目要的是「每个窗口的最大值和最小值」，开两个 deque 分别维护， 不要试图用一个队列同时管两头。

BISHI115　可匹配子段计数（简单）

数组 \(a\)（长 \(n\)）、\(b\)（长 \(m\)），对 \(a\) 的每个长度恰为 \(m\) 的连续子段 \(c\)， 定义匹配度 \(\operatorname{match}(c) = \sum_x \min(cnt_x(c), cnt_x(b))\)， 求 \(\operatorname{match} \ge k\) 的子段数。多组数据，\(\sum n, \sum m \le 2\times10^5\)。 题面见 BISHI115 原题（牛客）。

定长窗口 + 增量维护匹配度。关键是想清楚 \(\min(cnt_x(c), cnt_x(b))\) 怎么增量更新：

• 加入元素 \(x\) 时：若加入前 \(cnt_x(c) < cnt_x(b)\)，说明这个 \(x\) 还「有位置可占」， 匹配度 \(+1\)；否则是多余的，匹配度不变。
• 删除元素 \(y\) 时：先减 cnt，若减完后 \(cnt_y(c) < cnt_y(b)\)，说明刚才那个 \(y\) 是「占着位置的」，匹配度 \(-1\)。

import sys
from collections import Counter


def main():
    data = sys.stdin.buffer.read().split()
    p = 0
    t = int(data[p]); p += 1
    out = []
    for _ in range(t):
        n = int(data[p]); m = int(data[p + 1]); k = int(data[p + 2]); p += 3
        a = list(map(int, data[p:p + n])); p += n
        b = list(map(int, data[p:p + m])); p += m

        need = Counter(b)                 # b 里每个值的需求量
        cur = Counter()                   # 当前窗口里每个值的数量
        match = 0                         # 窗口与 b 的多重集合交的大小
        ans = 0
        for i in range(n):
            x = a[i]
            # 加入前 cur[x] < need[x] 说明 x 还有空位可占，min 会跟着 +1；否则是多余的
            if cur[x] < need[x]:          # 这个 x 能占住一个位置
                match += 1
            cur[x] += 1
            if i >= m:                    # 窗口长度固定为 m，多出一个就弹左端
                y = a[i - m]
                cur[y] -= 1
                # 减完仍 < need[y]，说明刚弹掉的那个 y 原本是占着位置的，min 要跟着 -1
                if cur[y] < need[y]:      # 弹掉的是「占位」的那个
                    match -= 1
            if i >= m - 1 and match >= k:    # 窗口填满（i >= m-1）后才是合法子段
                ans += 1
        out.append(ans)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

三个要点：

• 「重排后至少 \(k\) 个位置相等」= 多重集合的交的大小，题面已经把它形式化成 \(\sum_x \min(cnt_x(c), cnt_x(b))\)，这一步想不通整题就废了。
• \(a_i \le 10^6\) 但 \(\sum n \le 2\times10^5\)：值域比元素数大得多， 所以用 Counter 而不是 list 桶（否则每组数据都要清空一个 \(10^6\) 的数组， 多组下直接 TLE）。这是 41-桶计数与离散化 讲的选型问题。
• 多组数据的 Counter 必须每组新建，绝不能复用后 clear() 之外的写法。

BISHI116　【模板】双指针（中等）

\(n \le 2\times10^5\)，\(0 \le a_i \le n\)。求所有最长的、元素两两不同的区间， 按 \(l\) 递增输出。 题面见 BISHI116 原题（牛客）。

这是 43.2 框架的直接应用，但多了一个「输出全部最优解」的要求。

关键洞察：对每个右端点 \(r\)，「以 \(r\) 结尾且元素互不相同」的最长区间是唯一的， 记作 \([l_r, r]\)。所有的最长区间必然都是这种形式，所以只需要在扫描过程中 把长度等于最大值的 \([l_r, r]\) 全部收集起来。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))

    last = [-1] * (n + 1)        # 值 -> 上一次出现的下标（题目保证 0 <= a_i <= n），-1 表示没出现过
    best = 0
    l = 0                        # 窗口左端；不变量：[l, r] 内元素两两不同
    segs = []
    for r in range(n):
        v = a[r]
        # 只有当上一次出现位置落在窗口内时才需要收缩；写成 l = last[v] + 1 会让 l 回退，破坏单调性
        if last[v] >= l:
            l = last[v] + 1      # 左端跳到上一次出现位置的右边
        last[v] = r
        length = r - l + 1       # 以 r 结尾的、元素互不相同的最长区间长度
        if length > best:
            best = length
            segs = [(l, r)]      # 出现更长的，之前收集的全作废
        elif length == best:
            segs.append((l, r))  # 并列最长，一起收好；l 随 r 单调不减，天然按 l 递增
    out = [str(len(segs))]
    out.extend("%d %d" % (l + 1, r + 1) for l, r in segs)
    sys.stdout.write("\n".join(out) + "\n")


main()

四个要点：

• l = max(l, last[v] + 1) 而不是 l = last[v] + 1： 代码里写成 if last[v] >= l 是同一件事。少了这个判断，遇到 「重复元素在窗口左边之外」时左端会回退，单调性被破坏，答案直接错。
• 值域 \([0, n]\) 用 list 桶存 last，比 dict 快 2–3 倍；数组要开 \(n+1\) 长。
• 收集全部最优解：> 时清空重来，== 时追加。因为 \(l\) 随 \(r\) 单调不减， 收集顺序天然满足题目要求的「\(l\) 递增」，不用再排序。
• 题目明说没有 SPJ，所以输出顺序必须严格按 \(l\) 递增——这里靠单调性白拿。

BISHI117　小苯的 IDE 括号问题（easy）（中等）

括号串里有一个光标 I，执行 \(k\) 次 backspace / delete，输出最终串。 backspace：若光标左边是 ( 且右边是 )，一次删掉这对；否则删左边一个字符。 delete：删右边一个字符。\(n, k \le 2\times10^5\)。 题面见 BISHI117 原题（牛客）。

光标问题的标准模型：两个栈（对顶栈）。光标左边的字符存在 left 栈里（栈顶靠近光标）， 右边的字符倒序存在 right 栈里（栈顶也靠近光标）。这样两种删除都是 \(O(1)\)：

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    s = data[2].decode()
    i = s.index("I")                      # 光标位置，s[i] 是那个 'I'
    left = list(s[:i])                    # 光标左侧，栈顶（末尾）最靠近光标
    right = list(s[i + 1:][::-1])         # 光标右侧倒序存，栈顶也最靠近光标

    for j in range(3, 3 + k):             # 前 3 个 token 是 n、k、s，操作从下标 3 开始
        op = data[j]
        if op == b"delete":
            if right:                     # 右侧为空时该操作无效果
                right.pop()               # 两个栈的栈顶都紧贴光标，删除因此是 O(1)
        else:                             # backspace
            # 光标左边是 '(' 且右边是 ')' 时优先成对删除，这一分支必须排在普通删除之前
            if left and left[-1] == "(" and right and right[-1] == ")":
                left.pop()                # 成对删除
                right.pop()
            elif left:                    # 否则退化成删左边一个字符；左侧为空则无效果
                left.pop()
    sys.stdout.write("".join(left) + "I" + "".join(reversed(right)) + "\n")


main()

• right 必须倒序存，否则删「右边第一个字符」是 list.pop(0)，\(O(n)\) 退化。 这正是「用两个栈模拟光标」这一模型存在的理由。
• 两种删除都要判空（「若左侧为空则无效果」）。
• 最终输出别忘了把 I 放回去，且 right 要再倒回来。

这题的标签是「双指针」，但更准确的说法是对顶栈—— 它和双指针共享同一个直觉：两个方向各自维护，中间是分界线。 相关模型见 32-栈。

BISHI118　相差不超过 k 的最多数（中等）

排序后双指针求最长合法段，是 43.2 框架最纯粹的实例。 完整代码与「为什么排序等价于最轻量的离散化」的讨论见 41-桶计数与离散化 §41.6。

BISHI119　小红的 01 子序列构造（easy）（中等）

01 串 \(s\)（\(n \le 2\times10^5\)），求任意一个区间 \([l, r]\)， 使子串里恰好有 \(k\ (k \le 10^{10})\) 个 01 子序列；无解输出 \(-1\)。 题面见 BISHI119 原题（牛客）。

单调性分析：记 \(f(l, r)\) 为窗口内 01 子序列个数。

• 固定 \(l\)，\(r\) 增大时 \(f\) 单调不减（每个新的 1 会带来「它左边 0 的个数」个新对）；
• 固定 \(r\)，\(l\) 增大时 \(f\) 单调不增。

于是：对每个 \(l\)，找最小的 \(r\) 使 \(f \ge k\)；若此时恰好 \(f = k\) 就是答案， 否则这个 \(l\) 一定无解（\(f\) 从 \(< k\) 一步跨过了 \(k\)）。由于最小的 \(r\) 随 \(l\) 单调不减， 两个指针各走一遍，总复杂度 \(O(n)\)。

增量维护是本题的技术核心：

• 右端加入 0：zeros += 1；加入 1：cnt += zeros。
• 左端弹出 0：zeros -= 1，然后 cnt -= 窗口内 1 的个数 （这个 0 与它右边的每个 1 各构成一对）。窗口内 1 的个数 \(=\) 窗口长度 \(-\) zeros，不用另外维护。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    s = data[2]

    r = 0            # 窗口是左闭右开 [l, r)，r 从不回退
    zeros = 0        # 窗口内 0 的个数
    cnt = 0          # 窗口内 "01" 子序列个数
    for l in range(n):
        # 固定 l 时 cnt 随 r 单调不减，所以一路右推到首次 cnt >= k 就停
        while r < n and cnt < k:
            if s[r] == 48:            # 字符 '0' 的 ASCII 码
                zeros += 1
            else:                     # '1'：与前面每个 0 各配成一对
                cnt += zeros
            r += 1
        if cnt == k:
            print(l + 1, r)           # 输出 1-indexed 闭区间：左端 l+1，右端就是开区间的 r
            return
        # 这里 cnt 要么 > k（一步跨过去了）要么 < k（串已扫完），本 l 无解，左端右移
        if s[l] == 48:                # 只有 0 离开窗口才会减少对数
            zeros -= 1
            cnt -= (r - l - 1) - zeros    # 窗口 [l+1, r) 的长度减去其中 0 的个数 = 1 的个数
    # l、r 各自单调右移，各走至多 n 步，总复杂度 O(n)
    print(-1)


main()

本题是 special judge（「输出任意一组均可」），本地按样例逐字符比对能过 只是因为这份贪心恰好先找到样例给出的那组解。 提交到 OJ 时不必担心，但自测时别因为输出和样例不同就以为写错了，见 20-输入输出处理 的 special judge 一节。

\(k\) 最大 \(10^{10}\)，超过 32 位——C++ 要 long long，Python 无所谓。

BISHI120　？？？（较难）

串 \(s\) 含小写字母与 ?，把每个 ? 替换成小写字母，使 \(t\) 成为 \(s\) 的子序列； 输出任意方案或报告无解。\(\sum|s| \le 2\times10^5\)。 题面见 BISHI120 原题（牛客）。

贪心 + 同向双指针：\(i\) 扫 \(s\)，\(j\) 指向 \(t\) 中待匹配的字符。 只要当前位能匹配（字符相同，或者是 ?）就立刻匹配——越早匹配越好， 因为把匹配位置尽量左移，留给后面的空间最大（这是子序列匹配的标准交换论证）。

# [片段] 本题为 special judge（答案不唯一），此处只给核心逻辑
j = 0                                 # j 指向 t 中下一个待匹配的字符
res = list(s)
for i, ch in enumerate(s):
    # 匹配位置尽量左移，给后面的字符留出最多的空间（子序列匹配的标准交换论证）
    if j < len(t) and (ch == t[j] or ch == "?"):
        res[i] = t[j]                 # 能匹配就立刻匹配
        j += 1
    elif ch == "?":
        res[i] = "a"                  # t 已匹配完或本位对不上，剩下的问号必须填成具体字母
print("YES" if j == len(t) else "NO")   # 扫完 s 后 j < len(t) 是唯一的无解情形

• 贪心正确性：若存在任何合法方案，那么「每一步都取最左可匹配位置」的方案也合法—— 逐位把方案中的匹配位置左移，不会破坏后续的可行性。
• 无解判定只有一条：扫完 \(s\) 后 \(j < |t|\)。
• 注意还没轮到匹配的 ?（\(j\) 已经用完）也要填上一个具体字母，不能留 ?。

本题的题解文件尚未建立，上面只是思路与核心片段，未经样例实测。

---

43.7　本章速查

场景	做法
最长满足条件的子段	同向双指针，best 在 while 外更新
最短满足条件的子段	同向双指针，best 在 while 内更新
有序数组两数之和	对撞指针
滑动窗口最值	单调队列，\(O(n)\)
窗口内不同元素数	Counter + 计数从 0→1 / 1→0 时增减
光标 / 中间插入删除	对顶栈（两个 list，一个倒序）
数组含负数求「和 \(\le k\)」	❌ 双指针失效，改前缀和 + 哈希
队列容器	必须 deque，list.pop(0) 是 \(O(n)\)

单调队列细节	值
队列存什么	下标（要靠它判过期）
求最大值	队列值单调递减，弹队尾用 <=
求最小值	队列值单调递增，弹队尾用 >=
队首过期判断	dq[0] <= i - k
开始输出	i >= k - 1

模板	位置
同向双指针（最长 / 最短）	§43.2
对撞指针	§43.3
单调队列	§43.4
窗口内不同元素计数	§43.5