# 第 23 章 线性结构技巧


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

## 学习目标

读完本章，你应当能够：

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

### 前置知识检查

| 你需要知道 | 在哪一节补齐 |
|---|---|
| 数组下标与区间表示（闭区间 `[l, r]` 与半开区间 `[l, r)` 的差别） | 23.3.1 节统一约定并给出对照 |
| 循环的复杂度估算与摊还计数 | 第 22.2、22.4 节 |
| Python 列表切片、`deque` 的两端操作及其代价 | 23.4.2 节给出 `deque` 用法 |
| 求和号 `Σ` 的展开与换序 | 23.3.1、23.3.2 节逐行推导前缀和公式 |
| 方差 `E[X²] − μ²` 的口径、浮点相减可能产生微小负值 | 23.3.3 节与第 26.1 节 |
| 排序与比较器（元组字典序、严格弱序） | 23.5 节从零讲起 |

## 23.1 四种技巧的定位

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

| 技巧 | 消掉的那一重枚举 | 前提条件 | 复杂度 | 本书真题 |
|---|---|---|---|---|
| 相向双指针 | 枚举另一个端点 | 数据有序，或两侧移动的效果相反 | `O(N)`（排序后） | 见 23.2.1 |
| 同向双指针（滑动窗口） | 枚举窗口左端 | 缩左端时判据单调 | `O(N)` | 【2026-09-11 编程题 1】 |
| 前缀和 / 差分 | 重扫区间内部 | 运算是可减的（和、平方和、异或） | 预处理 `O(N)`、查询 `O(1)` | 【2026-09-04 编程题 1】 |
| 单调栈 / 单调队列 | 重扫窗口求最值 | 入队时被弹掉的元素永远不再需要 | `O(N)` | 【2026-09-11 编程题 1】 |
| 排序键 | 多趟分维排序 | 存在覆盖全部区分维度的全序 | `O(N log N)` | 【2026-09-09 编程题 1】 |

> [!IMPORTANT]
> 四种技巧共有一条**验证方法**：找出被消掉的那重枚举"在相邻两步之间的差异"，若这个差异可在 `O(1)` 内维护，就能省掉整重枚举——滑动窗口右端右移只多一个元素；`[l, r]` 与 `[l, r+1]` 的和只差一个元素；窗口右移只有一进一出。做不到 `O(1)` 维护，该技巧就不适用，硬套必然出错。

## 23.2 双指针：相向与同向

### 23.2.1 相向双指针

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

```python
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` 为右端点时最靠左的合法窗口，用它更新答案。写成骨架即：

```python
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
```

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

| 要素 | 问题 | 在折损窗口题中的体现 |
|---|---|---|
| 约束 | 窗口合法与否由什么决定？ | 折叠后内存 `≤ B` |
| 单调性 | 缩左端时约束变松还是变紧？ | 删任意一块都只会更省内存 |
| 最优性 | 每个右端点为什么只需看**最靠左**的合法左端？ | 多纳入一块得分不减 |

**单调性的两种形态**：形态 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：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]`：

```
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` 的边界特判。

```python
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
```
**可减性**是这个技巧的适用条件：只有存在逆运算的运算才能做前缀。

| 运算 | 是否可做前缀和 | 说明 |
|---|---|---|
| 加法（求和） | 可以 | 最常见 |
| 平方和 | 可以 | 用于 `O(1)` 算方差，见 23.3.3 |
| 异或 | 可以 | `x ⊕ x = 0`，可逆 |
| 乘法 | **不可以**（除法有零与精度问题） | 需改成前缀对数或放弃 |
| 最大值 / 最小值 | **不可以** | 没有逆运算，改用稀疏表或单调队列 |

### 23.3.2 二维前缀和

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

```
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]` 被减了两次，故加回来一次。

```python
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]
```

> [!WARNING]
> 二维前缀和最常见的错误是**四角公式下标写混**。可靠记忆是"**右下减左、减上、加回左上**"：四个角都取 `+1` 的那个位置，被减的两项分别"只减行"和"只减列"。另一个高频错误是在**空矩阵**（`n = 0` 或某行长度为 0）上访问 `a[0][0]` 导致 `IndexError`，构造 `P` 时就要处理。

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

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

```
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]`。

```python
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 单调栈：下一个更大元素

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

```python
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`。四种变体见下表。

| 目标 | 栈内单调性 | 弹栈条件 | 答案位置 |
|---|---|---|---|
| 右侧第一个更大 / 左侧第一个更大 | 递减 | 右侧 `<`、左侧 `<=` | 右侧看触发弹栈的 `i`，左侧看弹栈后的新栈顶 |
| 右侧第一个更小 / 左侧第一个更小 | 递增 | 右侧 `>`、左侧 `>=` | 同上 |

严格与不严格的差别取决于题目对相等元素的要求。对同一组数据求"左侧第一个严格更大元素"，弹栈条件用 `<=`：`[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）解决"定长滑动窗口的最大值/最小值"。它与单调栈的关键差别是：**队头还要能因窗口左端移动而失效**。

```python
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】第二问给出的是：

```python
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)` 按字典序比较就是一个全序；**若把比较器写成"净收益更大者优先"而净收益依赖窗口其他成员，序就可能被破坏，单调队列随之失效**。另外，比较器的语义必须是"**谁更适合当答案**"，因为队头代表当前窗口按该序的最优者；方向写反不会报错，只会静默给出错误答案。把栈与队列并列起来看：

| 结构 | 两端操作 | 队头/栈顶是什么 | 何时弹出尾部 | 代表问题 |
|---|---|---|---|---|
| 单调栈 | 只在一端进出 | 栈内"待解决者" | 新元素使栈顶失去成为答案的可能 | 下一个更大元素、柱状图最大矩形 |
| 单调队列（递减） | 两端进出 | 窗口最大值 | 新元素 `>=` 队尾 | 定长窗口最大值 |
| 单调队列（自定义序） | 两端进出 | 窗口内"最适合当答案"者 | 新元素按自定义序不劣于队尾 | 【2026-09-11 编程题 1】折损块 |

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

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

```python
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 下标升序排一次。

> [!WARNING]
> "叠加"题最常出错的不是各个技巧本身，而是**它们之间的接口**：单调队列用的左端下标是否与双指针的 `left` 保持同步？前缀和的索引是半开还是闭区间？排序后的次序与原始下标如何在输出时还原？**编码前把这些接口写在一张纸上**，比写完再调试快得多。

## 本章小结

| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| 相向双指针 | 正确性靠"整行/整列排除"论证，不是"移动一步试一次" | 数据未排序就按大小移动指针 |
| 滑动窗口的前提 | 缩左端时约束只可能变松（形态 A），右端固定时窗口越大越优（形态 B） | 对"平均值 ≥ T"这类非单调约束硬用滑动窗口 |
| 单调性论证 | 必须分别证明形态 A 与形态 B，缺一不可 | 只凭"看上去能缩"就动手写 |
| 前缀和约定 | `P[i]` 是"前 `i` 个元素之和"，区间和 `= P[r+1] − P[l]` | 用 `P[i] = a[0]+…+a[i]`，导致 `l=0` 需要特判 |
| 可减性 | 只有存在逆运算的运算才能做前缀（和、平方和、异或可以；乘积、最值不行） | 对最大值做前缀和，得到错误答案 |
| 二维前缀和 | `P[i][j] = 上 + 左 − 左上 + a[i−1][j−1]`；子矩阵和用四角容斥 | 四角公式下标写混；空矩阵未做保护 |
| 差分 | 区间加只需改 2 个点（二维 4 个角），最后前缀和还原 | 忘记 `d[r+1] -= v`，影响一直延续到数组末尾 |
| 前缀和的推广 | 0/1 化之后，前缀和就是"满足条件的元素个数" | 只把前缀和当成"求和工具" |
| 方差公式 | `σ² = E[X²] − μ²`，浮点相减可能为负，开方前截断到 0 | 忽略负方差导致 `math.sqrt` 抛异常 |
| 统计口径 | 总体标准差除以 `m`，样本除以 `m−1` | 用 `m−1` 算题面要求的总体口径 |
| 单调栈 | 栈内保持单调不变式；每个下标进出各一次，摊还 `O(n)` | 严格/不严格比较符号选错，相等元素的答案全错 |
| 单调队列 | 入队前弹掉"未来永远无用"的队尾；左端滑出时弹队头 | 用 `list.pop(0)`，把 `O(n)` 退化成 `O(n²)` |
| 自定义比较器 | 必须构成严格弱序，语义是"谁更适合当答案" | 方向写反，程序不报错但答案全错 |
| 排序键 | 数值维加负号把降序统一进升序；键应覆盖全部区分维度以保证全序 | 键不完整，输出顺序由排序稳定性决定，结果不确定 |

## 自测题

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

<details><summary>答案与解析</summary>
**可以用。** 用两个单调队列（一个递减维护最大值、一个递增维护最小值）在摊还 `O(1)` 内取得极差。**形态 A**：设窗口极差 `max − min > K`，删掉左端元素后窗口变小，最大值不会增大、最小值不会减小，故新极差 `max' − min' ≤ max − min`，**缩左端后极差不会变大**；若仍 `> K` 就继续缩，直到窗口只剩 1 个元素（极差为 0 ≤ K 必定合法），故内层 `while` 一定终止且不会漏解。**形态 B**：题目求"最长"，右端固定时长度 `right − left + 1` 随 `left` 减小而增大；若 `[left, right]` 合法，则任何 `[left', right]`（`left < left' ≤ right`）都合法（子窗口极差不超过父窗口极差），故只需取最靠左的合法左端。**错在哪**：只维护一个队列——极差需要同时知道最大值与最小值，缺少任何一边都会给出错误判据。
</details>

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

<details><summary>答案与解析</summary>
| `i` | `a[i]` | 入队前弹尾 | 队列（存下标） | 队头出窗？ | 窗口最大值 |
|---|---|---|---|---|---|
| 0 | 4 | — | `[0]` | 否 | 未成形 |
| 1 | 2 | 无（`4 > 2`） | `[0, 1]` | 否 | 未成形 |
| 2 | 7 | 弹出 1（`2 ≤ 7`）、弹出 0（`4 ≤ 7`） | `[2]` | 否 | `a[2] = 7` |
| 3 | 1 | 无（`7 > 1`） | `[2, 3]` | 否（`2 > 3−3 = 0`） | `a[2] = 7` |
| 4 | 9 | 弹出 3（`1 ≤ 9`）、弹出 2（`7 ≤ 9`） | `[4]` | 否 | `a[4] = 9` |
| 5 | 3 | 无（`9 > 3`） | `[4, 5]` | 否（`4 > 5−3 = 2`） | `a[4] = 9` |

结果 `[7, 7, 9, 9]`（逐窗验证 `4,2,7 → 7`、`2,7,1 → 7`、`7,1,9 → 9`、`1,9,3 → 9`）。**错在哪**：弹尾必须用 `<=`——相等的旧元素比新元素先离窗，留着它对未来窗口没好处还占位置；若题目要求"同值时取靠前的下标"，弹尾条件要改成严格 `<`，这正是最容易与题目口径冲突的地方。
</details>

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

<details><summary>答案与解析</summary>
预处理二维前缀和后查询 `O(1)`：`P = build_prefix_2d(a)` 耗时 `O(nm) = 10⁶`，每次 `S = rect_sum(P, r1, c1, r2, c2)`，总计 `O(q) = 10⁵`。**错在哪**：不做预处理而逐格相加是 `O(nm)`，`q` 次就是 `10⁵ × 10⁶ = 10¹¹`，远超安全线。**还需注意**：`n = 0` 或某行长度为 0 时访问 `a[0]` 会抛异常，需提前返回空前缀表；题面若给 `1-based` 行列号，转 `0-based` 时容易差 1，要写死在函数签名里；C++/Java 下 `n = m = 1000` 且元素达 `10⁹` 时总和可达 `10¹⁵`，必须用 64 位整数。
</details>

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

<details><summary>答案与解析</summary>
设差分数组 `d`，还原定义为 `a[i] = Σ_{t=0}^{i} d[t]`。操作前 `d` 相对基线全零，执行 `d[l] += v`、`d[r+1] -= v` 后分三段讨论：

```
对 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   （两处贡献恰好抵消）
```

因此只有 `l ≤ i ≤ r` 的元素被加上了 `v`。∎ **推广到多次操作**：差分是线性运算（`a` 与 `d` 之间是线性双射），多个区间修改可直接在 `d` 上叠加，最后一次性前缀和还原——这正是"批量区间修改"比逐次修改快的原因。**错在哪**：若 `r = n − 1`，`d[r+1]` 越界；解决方案是把 `d` 开到 `n + 1` 长度（多出的那一位不参与还原），如 23.3.3 节的代码所示。
</details>

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

<details><summary>答案与解析</summary>
**错误原因：形态 A 不成立**——缩左端可能让平均值**更低**。反例：`a = [10, 0, 0]`、`T = 4`，窗口 `[0, 2]` 的平均值是 `10/3 ≈ 3.33 < 4` 不合法；按该做法缩左端得到 `[1, 2]`，平均值是 `0`，比原来更低。缩左端非但不能恢复合法，还越缩越糟，内层 `while` 会一路缩到空窗口，然后被错误判定为"不存在合法窗口"（而 `[0,0]` 的平均值是 10，合法）。根因：平均值是**非单调**统计量，删掉高于均值的元素会让均值下降，删掉低于均值的元素却会让均值上升。**正确思路：转化为前缀和上的不等式**。设 `P[i] = Σ_{t<i} a[t]`，则 `(P[r+1] − P[l]) / (r+1 − l) ≥ T` 等价于 `P[r+1] − T·(r+1) ≥ P[l] − T·l`。令 `Q[i] = P[i] − T·i`，问题变成"**求最长的 `l < j` 使 `Q[j] ≥ Q[l]`**"，即求最远的一对满足偏序的下标：构造 `Q`，预处理前缀最小值 `M[i] = min(Q[0..i])`（单调不增），再对每个 `j` 从大到小枚举，用双指针或二分找最小的 `l` 使 `Q[l] ≤ Q[j]`，`O(n)` 或 `O(n log n)`。关键不是"技巧用错"，而是**没有先验证单调性前提**。
</details>

**Q6**（设计）对数组每个位置 `i` 输出它**左侧第一个严格大于它的元素的下标**，不存在输出 `-1`。写出代码并说明 `[2, 2, 3]` 的输出。

<details><summary>答案与解析</summary>
```python
def prev_greater(a):
    """每个位置左侧第一个严格更大元素的下标，不存在记 -1。从左往右扫，栈内严格递减，弹栈后的新栈顶就是答案。"""
    n, res, stack = len(a), [-1] * len(a), []    # 存下标，值严格递减
    for i in range(n):
        while stack and a[stack[-1]] <= a[i]:    # 严格更大 ⟹ 弹掉所有 <= a[i] 的栈顶
            stack.pop()
        res[i] = stack[-1] if stack else -1      # 栈顶即左侧第一个严格更大者
        stack.append(i)
    return res
```

对 `a = [2, 2, 3]`：`i = 0` 栈空故 `res[0] = -1`，栈变 `[0]`；`i = 1` 弹出 0（`2 <= 2`）后栈空故 `res[1] = -1`，栈变 `[1]`；`i = 2` 弹出 1（`2 <= 3`）后栈空故 `res[2] = -1`。输出 `[-1, -1, -1]`，因为题目要求**严格**大于：`a[0] = 2` 不大于 `a[1] = 2`，故不能作为 `i = 1` 的答案；更进一步，`a[1]` 比 `a[0]` 更靠右且值相等，**未来任何位置只要能看到 `a[0]` 就一定能看到 `a[1]`**，所以 `a[0]` 永久无用。**错在哪**：若把口径记成"不严格大于"，弹栈条件会变成 `a[stack[-1]] < a[i]`，此时 `i = 1` 不弹栈（`2 < 2` 为假）并记录 `res[1] = 0`，输出 `[-1, 0, -1]`——同一组数据、同一个结构，仅因一个比较符号，答案完全不同。
</details>

## 与真题的关联

| 真题 | 考查角度 | 对应本章小节 |
|---|---|---|
| 【2026-09-04 编程题 1】时间序列清洗与特征评分 | 前缀和把窗口 `μ`、`σ` 降到 `O(1)`；`σ²` 相减可能为负需截断；总体口径除以 `m` | 23.2.4、23.3.1、23.3.3 |
| 【2026-09-11 编程题 1】端侧大模型动态权重剪枝管理器 | 双指针 + 单调队列；折损窗口的形态 A/形态 B 论证；自定义比较器两级优先级 | 23.2.2、23.2.3、23.4.2、23.4.3 |
| 【2026-09-09 编程题 1】动态 KV 缓存稀疏优化 | 全局池 + 多级排序键 `(−score, l, h, t)`；末尾按 token 下标重排 | 23.5、23.6 |
| 【2026-09-02 编程题 1】滑动窗口注意力机制 | 窗口掩码只依赖 `(seq_len, ω)`，两端截断自动完成 | 23.2.2、23.2.4 |
| 【2026-09-11 编程题 2】文档片段相关性判定 | 距离比较用平方 + 容差，避免开根号引入误差 | 23.3.1（比较平方等价于比较原值） |
| 【2026-08-26 编程题 2】多头注意力双向整数 RNN | 按空白取词的输入解析与行边界不对齐 | 23.3.4；详见第 26.4 节 |
| 【2026-08-26 编程题 1】矩阵乘法的分块累加 | 分块边界与半开区间口径的一致处理 | 23.3.1、23.3.2 |

## 延伸阅读

- Sedgewick & Wayne，《Algorithms》第 1.4、4.3 节——双指针与滑动窗口的工程化表述。
- 《Competitive Programmer's Handbook》第 9 章"Range Queries"——前缀和、差分、稀疏表家族及二维扩展。
- LeetCode 专题：单调栈（"Next Greater Element"系列）、单调队列（"Sliding Window Maximum"）。


---

> 作者: [破戒僧](https://onlyblacktea.cn)  
> URL: https://onlyblacktea.cn/book/ai/ch23/  

