第 23 章 线性结构技巧

阵列与序列是机考编程题的主战场。本章把四件"降一维"的工具讲透：双指针与滑动窗口、前缀和与差分、单调栈与单调队列、排序键。它们的共同点是——把原本"两重枚举区间"的 O(N²) 做法压到 O(N)（排序键则是把多趟排序压成一趟），代价是必须先证明某个单调性。证明不成立却硬用，就会得到一个跑得飞快但答案错误的程序。

学习目标

读完本章，你应当能够：

1. 区分相向双指针与同向双指针（滑动窗口），并判断题目适用于哪一种；
2. 对"能否用滑动窗口"给出单调性论证：分别证明缩左端时判据只可能变松（形态 A）、右端固定时窗口越大越优（形态 B）；
3. 写出一维与二维前缀和，用 O(1) 回答任意区间、任意子矩阵的求和查询，并判断一个运算是否可减；
4. 用差分数组把"多次区间整体加同一个值"压成每处 O(1) 的标记，最后一次前缀和还原；
5. 用单调栈求"左右第一个更大/更小元素"、用单调队列求"滑动窗口最值"，并说明每个下标进出各一次；
6. 在"最优者"不能用大小直接比较时，构造满足严格弱序的自定义比较器；
7. 把多级优先级编码进 (−score, l, h, t) 这样的元组键，一次排序得到唯一确定的次序。

前置知识检查

23.1 四种技巧的定位

所谓"降一维"，指的是把一层 O(N) 的枚举消掉。

23.2 双指针：相向与同向

23.2.1 相向双指针

两个指针从两端向中间靠拢，正确性依赖一个排除性论证：每一步排除掉一批不可能的答案。典型场景是有序数组的两数之和：给定已排序数组 a 与目标 T，判断是否存在 i < j 使 a[i] + a[j] = T。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def two_sum_sorted(a, target):
    """有序数组两数之和。每轮排除一整行（或一整列），故至多 n 步。"""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1      # a[lo] 与任何 j <= hi 相加都 <= s < target ⟹ 整行排除
        else:
            hi -= 1      # 对称地，a[hi] 与任何 i >= lo 相加都 >= s > target ⟹ 整列排除
    return None

为什么正确：设当前和 s < target。对任意的 j ≤ hi，由有序性有 a[j] ≤ a[hi]，于是 a[lo] + a[j] ≤ a[lo] + a[hi] = s < target，即任何以 lo 为左端点的配对都不可能等于 target，可以安全放弃 lo。这就是排除性论证的标准形态：证明某一整行（或整列）候选被排除，而不是只排除一个点；说不出"整行被排除"，双指针的正确性就还没建立。两类常见误用：其一，数据未排序却按大小关系移动指针，此时 a[lo] + a[j] ≤ a[lo] + a[hi] 不成立，“整行排除"的论证崩塌；其二，题目要找的不是"一对"而是"最接近的一对”，排他性论证要重做——s < target 时 lo 仍右移，但要用 s 更新"当前最佳"且不能提前返回。遇到"最接近"“第 k 个"这类目标时，先写清楚指针移动后"哪一批候选被永久排除”，再动笔。

23.2.2 滑动窗口的三要素与骨架

同向双指针的区间 [left, right] 即一个窗口：右端每右移一格就把 a[right] 纳入并增量维护状态；当窗口不合法时从左端吐出元素直到重新合法；此刻 [left, right] 就是以 right 为右端点时最靠左的合法窗口，用它更新答案。写成骨架即：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def sliding_window(a, ok):
    """通用骨架：ok(left, right) 判断窗口是否仍满足约束。
    前提是"缩左端只能让约束更容易满足"（形态 A），否则内层 while 会缩掉合法窗口。"""
    n = len(a)
    left, best = 0, 0
    for right in range(n):
        ...                          # ① 纳入 a[right]，增量维护窗口状态
        while left <= right and not ok(left, right):
            ...                      # ② 不合法时从左端吐出元素（形态 A 保证终止）
            left += 1
        best = max(best, right - left + 1)   # ③ 此刻是最靠左的合法窗口（形态 B 保证最优）
    return best

一个滑动窗口解法必须回答三个问题，缺一不可。

单调性的两种形态：形态 A（约束单调）指窗口不合法时缩左端必定能恢复合法，从而内层 while 一定终止且不会漏解；形态 B（目标单调）指右端固定时扩大窗口不会让目标值变差，从而只需取"最靠左的合法左端"这一个候选，不必枚举所有左端。形态 A 保证算法正确，形态 B 保证算法充分。

23.2.3 完整案例：折损窗口的单调性论证

【2026-09-11 编程题 1】第二问：窗口内允许把重要度最小的块深度量化，其内存减半（向下取整）、重要度归零。窗口合法当且仅当 mem − (m_k − ⌊m_k / 2⌋) ≤ B，其中 k = argmin s（并列时取 m 更大者）。形态 A（缩左端一定变松）：设删除左端块 x，分两种情形。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

情形 1：x ≠ k
  折损块仍是 k ⟹ 省下的内存 (m_k − ⌊m_k/2⌋) 不变
  而总内存从 mem 降到 mem − m_x，m_x ≥ 1 > 0
  ⟹ 左边减少的比右边多，条件更容易满足
情形 2：x = k
  总内存减少 m_k；同时折损块换了别人（或窗口变空），省下的内存变成 ≤ (m_k − ⌊m_k/2⌋)
  注意右边不减反增：左边少了 m_k，右边最多减少 (m_k − ⌊m_k/2⌋) = ⌈m_k/2⌉
  而 m_k ≥ ⌈m_k/2⌉，故左边减少得更多 ⟹ 同样更容易满足

形态 B（右端固定时左端越靠左越好）：只考虑合法的窗口，多纳入一块 y。
情形 1：y 不成为新的折损块 ⟹ 得分变化 = +s_y > 0（s_y ≥ 1），得分增加
情形 2：y 成为新的折损块（说明 s_y < s_k）
  原得分 = Σ窗口 s − s_k；新得分 = Σ窗口 s + s_y − s_y = Σ窗口 s；两者之差 = s_k > 0

两种情形都得出"更容易满足"（形态 A）与"得分只增不减"（形态 B），所以一旦超预算，不断缩左端一定能恢复合法，且右端固定时窗口越大得分越高，只需看最靠左的合法左端。

23.2.4 单调性不成立的反例

给定正整数数组，求最长的连续子数组使最大值与最小值之差 ≤ K，这可以用滑动窗口（缩左端时窗口变小、极差不会变大）。若把条件改成"平均值 ≥ T"，对 a = [10, 0, 0]、T = 4：窗口 [0,2] 的平均值是 10/3 ≈ 3.33 < 4 不合法，缩左端得 [1,2]、平均值是 0，反而更不合法。缩左端把那个"拉高平均值"的 10 吐了出去，形态 A 不成立：内层 while 会一路缩到空窗口，然后被错误判定为无解（而 [0,0] 的平均值是 10，合法）。根因是平均值非单调——删掉高于均值的元素让均值下降，删掉低于均值的元素却让均值上升。这类问题要转化为前缀和上的偏序问题（见自测题 Q5）。判断能否用滑动窗口，只问一句：“把左端元素丢掉之后，约束会更难满足吗？” 答案是"可能更难"就不要用；单调约束有和不超过 B（元素为正）、极差不超过 K、不同字符数不超过 K，非单调约束有平均值阈值、中位数阈值、任何"去掉元素反而变差"的指标。

23.3 前缀和与差分

23.3.1 一维前缀和与可减性

采用半开区间约定（最不易出错），P[i] 表示前 i 个元素之和，于是闭区间 [l, r] 的和是 P[r+1] − P[l]：

1
2
3
4

P[0] = 0,  P[i] = P[i−1] + a[i−1] = a[0] + … + a[i−1]     （i ≥ 1）

验证：a = [3, 1, 4, 1, 5]，P = [0, 3, 4, 8, 9, 14]
      a[1..3] = 1 + 4 + 1 = 6 = P[4] − P[1] = 9 − 3  ✓

为什么这个约定更好：P[i] 是"前 i 个之和"，于是"前 r+1 个"减"前 l 个"自然是 l..r 这 r−l+1 个元素。若改用 P[i] = a[0]+…+a[i]，公式变成 P[r] − P[l−1]，多出一个 l = 0 的边界特判。

1
2
3
4
5
6
7

def build_prefix(a):
    """返回长度 n+1 的前缀和：P[i] 是前 i 个元素之和。
    多留一位 P[0]=0，使区间 [l, r] 的和恒为 P[r+1]-P[l]，无需特判 l=0。"""
    p = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        p[i + 1] = p[i] + x
    return p

可减性是这个技巧的适用条件：只有存在逆运算的运算才能做前缀。

23.3.2 二维前缀和

对矩阵 a（n 行 m 列），递推与查询都是容斥：

1
2
3
4
5

P[i][j] = Σ_{r<i} Σ_{c<j} a[r][c]        （P 形状 (n+1) × (m+1)，首行首列全 0）
P[i][j] = P[i−1][j] + P[i][j−1] − P[i−1][j−1] + a[i−1][j−1]

子矩阵 a[r1..r2][c1..c2]（闭区间）的和 = 四角公式：
S = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]

几何解释：P[r2+1][c2+1] 覆盖整块大矩形，减去上方条带 P[r1][c2+1] 与左方条带 P[r2+1][c1]，其中左上角 P[r1][c1] 被减了两次，故加回来一次。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def build_prefix_2d(a):
    """二维前缀和，行列各多留一位 0，使子矩阵求和无边界特判"""
    n, m = len(a), len(a[0]) if a else 0
    p = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n):
        for j in range(m):
            # 容斥：上方 + 左方 − 重复扣掉的左上角 + 当前元素
            p[i + 1][j + 1] = p[i][j + 1] + p[i + 1][j] - p[i][j] + a[i][j]
    return p


def rect_sum(p, r1, c1, r2, c2):
    """闭区间子矩阵 a[r1..r2][c1..c2] 的和，O(1)"""
    return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1]

23.3.3 窗口均值与标准差降到 O(1)，以及差分的区间修改

【2026-09-04 编程题 1】第二步要对每个点算"以它为中心的窗口"的均值 μ 与总体标准差 σ。w 可取到 N − 1，逐点重扫是 O(Nw)；用和与平方和的前缀和降为 O(1)：

1
2
3

P1[i] = Σ_{t<i} v_t，  P2[i] = Σ_{t<i} v_t²
窗口 [lo, hi]（闭区间），点数 m = hi − lo + 1：
  μ  = (P1[hi+1] − P1[lo]) / m        σ² = (P2[hi+1] − P2[lo]) / m − μ²

σ² 的公式来自 Var = E[X²] − (E[X])²：(P2 区间和)/m 就是 E[X²]。两个必须处理的数值细节：其一，负方差——E[X²] − μ² 是相近浮点数相减，可能得到 −1e−16 之类的负值，开方前必须截断到 0，否则 math.sqrt 抛 ValueError；其二，总体口径 vs 样本口径——题面要求除以 m（总体）而非 m − 1（样本），小窗口下差异显著（m = 3 时差 22%），是本题主要分差点。

差分解决另一半问题：多次对区间整体加同一个值，最后一次性输出。定义 d 使 a 是 d 的前缀和，即 d[0] = a[0]、d[i] = a[i] − a[i−1]。对区间 [l, r] 整体加 v 只需两处修改，因为还原时 a[i] = Σ_{t≤i} d[t]：在 d[l] 加 v 会让所有 i ≥ l 的前缀和增加 v，在 d[r+1] 减 v 又把 i ≥ r+1 的部分抵消回去，净效果恰好是"只有 [l, r] 被加上 v"。

区间 [1, 3] 加 5，作用在差分上（只有两处非零，还原后恰好区间被加 5）：下标 0 到 4 的 d 是 [0, +5, 0, 0, −5]，还原出的增量是 [0, +5, +5, +5, 0]。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def range_add(a, ops):
    """ops 是一串 (l, r, v) 表示对闭区间 [l, r] 整体加 v。
    全部修改 O(len(ops))，最后 O(n) 还原，比逐次修改的 O(len(ops)·n) 快得多。"""
    n = len(a)
    d = [0] * (n + 1)              # 多留一位，避免 r+1 == n 时越界
    for l, r, v in ops:
        d[l] += v
        d[r + 1] -= v              # 抵消 l 之后的持续影响
    res, delta = a[:], 0
    for i in range(n):
        delta += d[i]
        res[i] += delta
    return res

二维差分对矩形 [r1..r2][c1..c2] 加 v 的四角是 d[r1][c1] += v、d[r1][c2+1] −= v、d[r2+1][c1] −= v、d[r2+1][c2+1] += v，还原时做一次二维前缀和。注意符号：两个减、一个加，恰好与二维前缀和的容斥公式同构；一维改 2 个点、二维改 4 个角，代价与"区间覆盖计数"这类应用都由此展开。

23.3.4 前缀和的另一个用法：把"计数"变成"查表"

把满足条件的元素置 1、不满足置 0，则 P[i] 表示"前 i 个元素中有多少个满足条件"：a = [1,0,1,1,0,1] 对应 P = [0,1,1,2,3,3,4]，区间 [1,4] 内满足条件的个数是 P[5] − P[1] = 3 − 1 = 2。把"计数"与"求和"统一起来是前缀和技巧最重要的观念跃迁：只要一个量满足"可加可减"，就值得做前缀。

23.4 单调栈与单调队列

23.4.1 单调栈：下一个更大元素

单调栈解决的问题：对每个元素，求它**左/右侧第一个比它大（或小）**的元素。

1
2
3
4
5
6
7
8
9

def next_greater(a):
    """每个元素右侧第一个严格更大元素的下标，不存在记 -1。栈内值严格递减，栈顶即尚未找到答案者中最靠右的。"""
    n = len(a)
    res, stack = [-1] * n, []        # 存下标：需要下标才能写入答案
    for i in range(n):
        while stack and a[stack[-1]] < a[i]:
            res[stack.pop()] = i     # i 就是栈顶元素的右侧第一个更大元素
        stack.append(i)
    return res

栈内单调不变式：每次入栈前把所有比 a[i] 小的栈顶弹掉，所以栈中从底到顶严格递减；这个不变式在循环的每一步都成立，它正是算法的正确性核心。摊还代价 O(n)：每个下标入栈一次、出栈至多一次，故 while 内 pop 的总次数不超过 n。四种变体见下表。

严格与不严格的差别取决于题目对相等元素的要求。对同一组数据求"左侧第一个严格更大元素"，弹栈条件用 <=：[2, 2, 2] 输出 [-1, -1, -1]；把数据换成 [2, 2, 3] 仍输出 [-1, -1, -1]（2 不大于 3，3 左侧无更大者）。改成"不严格大于"后弹栈条件退化为 <：[2, 2, 2] 输出 [-1, 0, 1]，[2, 2, 3] 输出 [-1, 0, -1]（i = 2 时 2 < 3 把前两个都弹掉）。同一组数据、同一个结构，仅因一个比较符号，答案完全不同——写代码前先手工推一遍。

23.4.2 单调队列：窗口最值

单调队列（monotonic deque）解决"定长滑动窗口的最大值/最小值"。它与单调栈的关键差别是：队头还要能因窗口左端移动而失效。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from collections import deque

def window_max(a, k):
    """返回每个长度为 k 的窗口的最大值。队列内下标对应的值递减，队头即当前窗口最大值。"""
    res, q = [], deque()             # 存下标；deque 的 popleft/append 均为 O(1)
    for i, x in enumerate(a):
        # 队尾不比新元素大 ⟹ 它先离开窗口且值更小，今后轮不到它当最大值，可永久丢弃
        while q and a[q[-1]] <= x:
            q.pop()
        q.append(i)
        if q[0] <= i - k:            # 队头已滑出窗口
            q.popleft()
        if i >= k - 1:               # 窗口成形后记录答案
            res.append(a[q[0]])
    return res

“入队弹尾"的贪心论证：设队尾下标 j、新元素 i（j < i）且 a[j] <= a[i]。只要 j 还在窗口内，i 也一定在窗口内（因 i > j）；在两者共存的每个窗口里都有 a[i] >= a[j]，所以 j 永远不会成为最大值；等到 i 滑出窗口时 j 早就滑出了。故 j 在任何未来窗口里都不可能成为答案，可以安全永久删除。这个论证的形态与单调栈完全一致：证明被删除的元素"在未来永远无用”；凡是能给出这类论证的场景都可以用单调结构。另外，list.pop() 是 O(1) 但 list.pop(0) 是 O(n)（需要整体搬移），deque.popleft() 才是 O(1)；在 O(n) 的算法里混入一个 O(n) 操作，整体退化到 O(n²)。

23.4.3 自定义比较器与单调结构的统一视角

当"谁更适合当窗口最优者"不能直接用大小比较时，需要传入自定义比较器，这出现在两种场景：多级比较（重要度最小者优先，相同时内存更大者优先，省下的内存更多）、动态键（元素的"有效值"依赖窗口内其他信息）。【2026-09-11 编程题 1】第二问给出的是：

1
2
3
4
5
6

def better_fold(s, m, i, j):
    """块 i 是否比块 j 更适合折损：
    s 更小者优先；s 相同时 m 更大者优先（省下的内存 m - m//2 更多）。"""
    if s[i] != s[j]:
        return s[i] < s[j]
    return m[i] > m[j]

关键改动：入队弹尾条件从 a[q[-1]] <= x 变成 not better_fold(s, m, q[-1], right)，即"队尾不比新块更适合折损"时弹掉它。自定义比较器必须构成严格弱序：传递性（better(a,b) and better(b,c) ⟹ better(a,c)）与反对称性（better(a,b) 与 better(b,a) 不能同时为真）。上例满足，因为 (s, −m) 按字典序比较就是一个全序；若把比较器写成"净收益更大者优先"而净收益依赖窗口其他成员，序就可能被破坏，单调队列随之失效。另外，比较器的语义必须是"谁更适合当答案"，因为队头代表当前窗口按该序的最优者；方向写反不会报错，只会静默给出错误答案。把栈与队列并列起来看：

23.5 排序键：把多级优先级编码进一个元组

题目给出多级优先级（“分数降序，同分时层升序，再同则头升序、token 升序”）时，不要写多趟排序或复杂比较函数，而是构造一个元组键，一次 sort() 搞定。核心技巧是取负号：Python 的 sort() 只支持升序，把某一维变成降序就写负号——reverse=True 只反转整体，不能只反转一维。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def build_ranked_candidates(scores, L, H, N, cur_pos):
    """把所有候选编码成 (排序键, 载荷) 并一次排好。
    负号把"分数降序"统一进升序排序，于是四级优先级一次完成。"""
    cands = []
    for l in range(L):
        for h in range(H):
            row = scores[l][h]
            for t in range(N):
                if t == cur_pos:          # 正在生成的 token 是刚性开销，先单独占位
                    continue
                cands.append((-row[t], l, h, t))
    cands.sort()                          # 全序 ⟹ 结果唯一，与实现细节无关
    return cands

【2026-09-09 编程题 1】的键就是 (-score, l, h, t)：分数降序写作 −score（分数越高键越小越靠前），层 l、头 h、token t 都直接升序。元组比较是字典序——先比第一维，相等才比第二维，以此类推——因此这个键天然实现了多级优先级。为什么"全序"很重要：若排序键不能区分两个候选（键完全相等），它们的相对顺序就取决于排序算法的稳定性与输入原始顺序；在键里含浮点的场景中，这会让结果不确定。构造一个覆盖全部区分维度的键（如上例连 t 都放进去）就保证了输出唯一；反过来，若题目要求"同分时取序号靠前者"而键里已包含序号，直接排序即可。

23.6 组合套路：真实题目往往是两种技巧叠加

真题很少只考一种技巧。叠加一：前缀和 + 滑动窗口【2026-09-04 编程题 1】——窗口右端右移时用前缀和 O(1) 得到新窗口的 μ、σ，再用它们判定当前点是否为异常值；窗口大小由题面固定，不需要"缩左端"这一步。叠加二：双指针 + 单调队列【2026-09-11 编程题 1】——双指针维护"内存预算合法"的窗口，单调队列维护"窗口内最该折损的块"，两者的左端必须同步移动：窗口缩了，队列里已出窗的元素也要弹出。这里的同步是易错点：队列的失效判定必须用"该下标是否已滑出当前窗口"，而当前窗口的左端由双指针维护，所以弹出条件要与 left 比较，而不是与"上一个窗口的左端"或"队列自己记录的历史左端"比较。叠加三：排序 + 贪心 + 多级键【2026-09-09 编程题 1】——多级优先级的全局竞争一次全局排序（键含负号）解决，名额分配取排序结果的前 remaining 个，分组输出时每个头再按 token 下标升序排一次。

本章小结

自测题

Q1（推导）给定正整数数组 a 与常数 K，判断"最长连续子数组，其中最大值与最小值之差 ≤ K"能否用滑动窗口，并给出完整的单调性论证。

Q2（计算）对数组 a = [4, 2, 7, 1, 9, 3] 求所有长度 k = 3 的窗口最大值，并逐步写出单调队列的状态。

Q3（设计）给定矩阵 a（n × m）与 q 次查询，每次查询一个子矩阵的元素之和，n, m ≤ 1000、q ≤ 10⁵。设计解法并分析复杂度。

Q4（推导）证明：对区间 [l, r] 整体加 v 的差分操作，还原后恰好只有 [l, r] 内的元素被加上 v。

1
2
3

对 i < l：      a[i] = Σ_{t≤i} d[t] = 0                          （l 尚未进入求和范围）
对 l ≤ i ≤ r：  a[i] = Σ_{t≤i} d[t] = d[l] = v                   （r+1 尚未进入求和范围）
对 i > r：      a[i] = Σ_{t≤i} d[t] = d[l] + d[r+1] = v − v = 0   （两处贡献恰好抵消）

Q5（辨析）“给定正整数数组，求最长的连续子数组，使其元素平均值 ≥ 阈值 T。“有人提出用滑动窗口：右端右移，若平均值小于 T 就缩左端。指出该做法为什么错误，并给出正确思路。