第 6 章栈、队列、堆与哈希专题#

本章目标：深入掌握四类高频结构在算法题中的模型化用法：单调栈、单调队列、优先队列和哈希状态。

6.1 学习目标#

掌握单调栈求最近更大/更小元素。
掌握单调队列维护滑动窗口最值。
掌握堆在动态最值和最短路中的用法。
掌握哈希表计数、去重和状态压缩。
能分析每个元素只进出一次带来的 $O(n)$ 复杂度。

6.2 单调栈#

单调栈维护一个单调序列。它解决的问题通常是：对每个位置，找左边或右边第一个比它大/小的元素。

以找右边第一个更大元素为例：

1
vector<int> ans(n, -1);
2
stack<int> st;
3
for (int i = 0; i < n; i++) {
4
    while (!st.empty() && a[i] > a[st.top()]) {
5
        ans[st.top()] = i;
6
        st.pop();
7
    }
8
    st.push(i);
9
}

每个下标最多入栈一次、出栈一次，所以总复杂度是 $O(n)$ 。

6.3 柱状图最大矩形#

对每个柱子 i，如果知道左边第一个比它矮的位置 L 和右边第一个比它矮的位置 R，则以 i 为最矮柱子的最大矩形面积为：

area_i = h_i \cdot (R_i - L_i - 1)

用单调栈可在线性时间求所有 L 和 R。

6.4 单调队列#

滑动窗口最大值：队列中保存下标，并保证对应值单调递减。

1
deque<int> q;
2
for (int i = 0; i < n; i++) {
3
    while (!q.empty() && q.front() <= i - k) q.pop_front();
4
    while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
5
    q.push_back(i);
6
    if (i >= k - 1) ans.push_back(a[q.front()]);
7
}

队首永远是当前窗口最大值下标。

6.5 堆的高级用法#

6.5.1 Top K#

维护大小为 k 的小根堆。遍历元素 x：

堆未满：直接加入。
x 大于堆顶：弹出堆顶，加入 x。
否则忽略。

最终堆中是前 k 大元素。

6.5.2 双堆维护中位数#

大根堆 small 保存较小一半。
小根堆 large 保存较大一半。
保证 $|size(small)-size(large)| \le 1$ 。

中位数由堆顶得到。

6.6 哈希计数#

两数之和：遍历 x，检查 target - x 是否出现过。

1
unordered_map<int, int> cnt;
2
for (int x : a) {
3
    if (cnt[target - x] > 0) return true;
4
    cnt[x]++;
5
}

哈希的核心是把“过去的信息”压缩成能快速查询的表。

6.7 状态哈希#

有些搜索状态是数组、字符串或棋盘，可以编码为字符串或整数作为哈希键。

例如 8 数码棋盘：

可编码为字符串 123456780。

状态哈希常用于：

BFS 判重。
记忆化搜索。
子串去重。
图状态压缩。

6.8 字符串哈希简述#

多项式哈希：

H(s)=\sum_{i=0}^{n-1} s_i p^i \bmod M

子串哈希可用前缀哈希快速计算：

H(l,r)=H(r)-H(l)\cdot p^{r-l}

哈希有碰撞概率，严谨场景可用双哈希。

6.9 易错点#

单调栈中存值还是存下标混乱。
单调队列忘记删除过期下标。
堆中旧元素未删除导致答案错误。
哈希表使用默认值造成逻辑误判。
字符串哈希忘记处理负数取模。
状态编码不唯一。

6.10 练习#

求每个元素右侧第一个更大元素。
求柱状图最大矩形。
维护滑动窗口最大值。
用双堆维护数据流中位数。
用哈希表做 BFS 判重。

ACM/OI 扩展：单调结构、可并堆与哈希技巧#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. 单调栈四种方向#

单调栈题要明确找左/右、第一个大/小。

目标	遍历方向	栈维护	弹出条件
右侧第一个更大	左到右	递减	当前 > 栈顶
右侧第一个更小	左到右	递增	当前 < 栈顶
左侧第一个更大	左到右	递减	栈顶 <= 当前
左侧第一个更小	左到右	递增	栈顶 >= 当前

要点：

相等时保留还是弹出取决于题目要严格还是非严格。

2. 单调队列优化 DP#

当转移中需要窗口最值，可用单调队列。

1
deque<int> q;
2
for (int i = 1; i <= n; ++i) {
3
    while (!q.empty() && q.front() < i - k) q.pop_front();
4
    if (!q.empty()) dp[i] = val(q.front(), i);
5
    while (!q.empty() && key(q.back()) >= key(i)) q.pop_back();
6
    q.push_back(i);
7
}

要点：

队列存候选下标，不只存值。
过期规则和单调规则分开写。

3. 懒删除堆#

堆不能删除任意元素，可用两个堆或计数表懒删除。

1
priority_queue<int> pq, del;
2
void erase(int x) { del.push(x); }
3
void normalize() {
4
    while (!pq.empty() && !del.empty() && pq.top() == del.top()) {
5
        pq.pop(); del.pop();
6
    }
7
}

要点：

适合滑动窗口中位数等需要删除旧元素的问题。
也可用 multiset 直接删除。

4. 自定义哈希防卡#

Codeforces 等平台可能卡 unordered_map，可加入 splitmix64。

1
struct custom_hash {
2
    static uint64_t splitmix64(uint64_t x) {
3
        x += 0x9e3779b97f4a7c15;
4
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
5
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
6
        return x ^ (x >> 31);
7
    }
8
    size_t operator()(uint64_t x) const {
9
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
10
        return splitmix64(x + FIXED_RANDOM);
11
    }
12
};
13
unordered_map<long long, int, custom_hash> mp;

要点：

不能保证绝对安全，但能降低被构造数据卡掉概率。

5. 栈模拟递归#

递归深度可能达到 2e5 时，C++ 容易爆栈，可改显式栈。

1
vector<int> order;
2
stack<pair<int,int>> st;
3
st.push({root, 0});
4
while (!st.empty()) {
5
    auto [u, p] = st.top(); st.pop();
6
    order.push_back(u);
7
    for (int v : g[u]) if (v != p) st.push({v, u});
8
}

要点：

树形 DP 若需要后序，可先得到 order 再反向遍历。

本章模板背诵清单#

能在 5 分钟内写出本章第一个核心模板。
能说出每个模板的时间复杂度和空间复杂度。
能说明模板不适用的反例。
能为模板构造 3 个边界样例。
能把模板改成 0-index 或 1-index 版本。

高频模板训练卡#

这一组训练卡用于把“06_栈_队列_堆_哈希”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：单调栈最近更大#

题目信号：需要维护最近关系、动态最值、快速查找或单调栈最近更大。
优先模板：使用单调栈最近更大模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用单调栈最近更大写一个模板题和一个变式题。

卡 2：单调栈最近更小#

题目信号：需要维护最近关系、动态最值、快速查找或单调栈最近更小。
优先模板：使用单调栈最近更小模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用单调栈最近更小写一个模板题和一个变式题。

卡 3：柱状图最大矩形#

题目信号：需要维护最近关系、动态最值、快速查找或柱状图最大矩形。
优先模板：使用柱状图最大矩形模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用柱状图最大矩形写一个模板题和一个变式题。

卡 4：单调队列窗口最值#

题目信号：需要维护最近关系、动态最值、快速查找或单调队列窗口最值。
优先模板：使用单调队列窗口最值模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用单调队列窗口最值写一个模板题和一个变式题。

卡 5：单调队列 DP#

题目信号：需要维护最近关系、动态最值、快速查找或单调队列 DP。
优先模板：使用单调队列 DP 模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用单调队列 DP 写一个模板题和一个变式题。

卡 6：双堆中位数#

题目信号：需要维护最近关系、动态最值、快速查找或双堆中位数。
优先模板：使用双堆中位数模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用双堆中位数写一个模板题和一个变式题。

卡 7：懒删除堆#

题目信号：需要维护最近关系、动态最值、快速查找或懒删除堆。
优先模板：使用懒删除堆模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用懒删除堆写一个模板题和一个变式题。

卡 8：Top K#

题目信号：需要维护最近关系、动态最值、快速查找或 Top K。
优先模板：使用 Top K 模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用 Top K 写一个模板题和一个变式题。

卡 9：合并 K 路#

题目信号：需要维护最近关系、动态最值、快速查找或合并 K 路。
优先模板：使用合并 K 路模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用合并 K 路写一个模板题和一个变式题。

卡 10：0-1 BFS 队列#

题目信号：需要维护最近关系、动态最值、快速查找或 0-1 BFS 队列。
优先模板：使用 0-1 BFS 队列模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用 0-1 BFS 队列写一个模板题和一个变式题。

卡 11：哈希计数#

题目信号：需要维护最近关系、动态最值、快速查找或哈希计数。
优先模板：使用哈希计数模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用哈希计数写一个模板题和一个变式题。

卡 12：哈希判重#

题目信号：需要维护最近关系、动态最值、快速查找或哈希判重。
优先模板：使用哈希判重模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用哈希判重写一个模板题和一个变式题。

卡 13：状态压缩哈希#

题目信号：需要维护最近关系、动态最值、快速查找或状态压缩哈希。
优先模板：使用状态压缩哈希模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用状态压缩哈希写一个模板题和一个变式题。

卡 14：字符串哈希#

题目信号：需要维护最近关系、动态最值、快速查找或字符串哈希。
优先模板：使用字符串哈希模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用字符串哈希写一个模板题和一个变式题。

卡 15：自定义 hash#

题目信号：需要维护最近关系、动态最值、快速查找或自定义 hash。
优先模板：使用自定义 hash 模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用自定义 hash 写一个模板题和一个变式题。

卡 16：二进制 Trie#

题目信号：需要维护最近关系、动态最值、快速查找或二进制 Trie。
优先模板：使用二进制 Trie 模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用二进制 Trie 写一个模板题和一个变式题。

卡 17：可并堆#

题目信号：需要维护最近关系、动态最值、快速查找或可并堆。
优先模板：使用可并堆模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用可并堆写一个模板题和一个变式题。

卡 18：表达式求值#

题目信号：需要维护最近关系、动态最值、快速查找或表达式求值。
优先模板：使用表达式求值模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用表达式求值写一个模板题和一个变式题。

卡 19：括号匹配#

题目信号：需要维护最近关系、动态最值、快速查找或括号匹配。
优先模板：使用括号匹配模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用括号匹配写一个模板题和一个变式题。

卡 20：LRU 链表哈希#

题目信号：需要维护最近关系、动态最值、快速查找或 LRU 链表哈希。
优先模板：使用 LRU 链表哈希模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用 LRU 链表哈希写一个模板题和一个变式题。

卡 21：滑动窗口哈希#

题目信号：需要维护最近关系、动态最值、快速查找或滑动窗口哈希。
优先模板：使用滑动窗口哈希模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用滑动窗口哈希写一个模板题和一个变式题。

卡 22：频率桶#

题目信号：需要维护最近关系、动态最值、快速查找或频率桶。
优先模板：使用频率桶模板。
核心不变量：每个元素的进入、离开和贡献变化都被准确维护。
复杂度目标：单调结构 O(n)，堆 O(n log n)，哈希平均 O(n)。
不适用场景：需要有序前驱后继时哈希不够；需要任意删除时普通堆不够。
实现检查：检查重复值、过期元素、哈希键唯一性、空结构访问。
边界样例：全相等、严格递增、严格递减、窗口大小 1。
训练题型：用频率桶写一个模板题和一个变式题。

本章赛前默写任务#

06_栈_队列_堆_哈希：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：单调栈#

识别信号：题面出现与“单调栈”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“单调栈”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：柱状图矩形#

识别信号：题面出现与“柱状图矩形”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“柱状图矩形”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：单调队列#

识别信号：题面出现与“单调队列”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“单调队列”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：滑动窗口最值#

识别信号：题面出现与“滑动窗口最值”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“滑动窗口最值”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：单调队列 DP#

识别信号：题面出现与“单调队列 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“单调队列 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：双堆中位数#

识别信号：题面出现与“双堆中位数”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“双堆中位数”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：懒删除堆#

识别信号：题面出现与“懒删除堆”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“懒删除堆”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：Top K#

识别信号：题面出现与“Top K”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Top K”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：合并 K 路#

识别信号：题面出现与“合并 K 路”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“合并 K 路”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：哈希计数#

识别信号：题面出现与“哈希计数”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“哈希计数”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：哈希判重#

识别信号：题面出现与“哈希判重”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“哈希判重”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：状态编码#

识别信号：题面出现与“状态编码”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“状态编码”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：字符串哈希#

识别信号：题面出现与“字符串哈希”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“字符串哈希”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：二进制 Trie#

识别信号：题面出现与“二进制 Trie”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“二进制 Trie”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：可并堆#

识别信号：题面出现与“可并堆”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“可并堆”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：表达式求值#

识别信号：题面出现与“表达式求值”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“表达式求值”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：单调栈#

识别信号：题面出现与“单调栈”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“单调栈”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：柱状图矩形#

识别信号：题面出现与“柱状图矩形”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“柱状图矩形”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：单调队列#

识别信号：题面出现与“单调队列”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“单调队列”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 20：滑动窗口最值#

识别信号：题面出现与“滑动窗口最值”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“滑动窗口最值”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 21：单调队列 DP#

识别信号：题面出现与“单调队列 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“单调队列 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 22：双堆中位数#

识别信号：题面出现与“双堆中位数”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“双堆中位数”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 23：懒删除堆#

识别信号：题面出现与“懒删除堆”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“懒删除堆”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 24：Top K#

识别信号：题面出现与“Top K”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Top K”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

ぬくぬくうちにゃ💤

第 6 章 栈、队列、堆与哈希专题#