《基础算法篇(4)：蓝桥杯常考点—数据结构（进阶）》主要聚焦于在蓝桥杯等编程竞赛中高频考察的数据结构及其高效应用。以下是本篇内容的系统梳理，适合用于学习和备考：
🧠 一、核心数据结构（进阶）
1. 单调栈（Monotonic Stack）
应用场景：
- 找左/右边第一个比当前元素大/小的位置（如：每日温度、柱状图最大矩形）
模板思路：
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[stk.top()] >= a[i]) stk.pop();
// stk.top()就是最近小于a[i]的索引
stk.push(i);
}
2. 单调队列（Monotonic Queue）
应用场景：
- 滑动窗口最大值/最小值问题
- 动态维护某区间最值（如最短路状态压缩）
模板思路：
for (int i = 0; i < n; i++) {
while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
q.push_back(i);
if (i - q.front() >= k) q.pop_front();
// q.front()为当前窗口内最小值的下标
}
3. 并查集（Union-Find Set）
常见题型：
- 判断连通性
- 处理集合归类问题（如冗余连接）
优化版本：路径压缩 + 按秩合并
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void unite(int x, int y) {
fa[find(x)] = find(y);
}
4. 树状数组（Binary Indexed Tree, Fenwick Tree）
用途：
- 区间求和、单点更新，常用于逆序对、前缀和等题目
- 时间复杂度：O(log n)
void add(int x, int v) {
while (x <= n) {
tree[x] += v;
x += x & -x;
}
}
int sum(int x) {
int res = 0;
while (x > 0) {
res += tree[x];
x -= x & -x;
}
return res;
}
5. 线段树（Segment Tree）
用途：
- 区间查询 + 单点/区间修改
- 支持RMQ（Range Minimum/Maximum Query）、区间加、区间覆盖等操作
实现方式：递归建树 + 查询 + 修改
void build(int u, int l, int r) {
if (l == r) {
tr[u] = a[l];
} else {
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid+1, r);
tr[u] = tr[u<<1] + tr[u<<1|1];
}
}
6. 栈与队列的嵌套使用
典型问题：
- 用两个栈模拟队列
- 用两个队列实现栈
- 表达式求值（逆波兰表达式）
🧮 二、拓展数据结构
1. 优先队列（堆）
- 用于求 Top-K、大根堆、小根堆、Dijkstra 算法等
priority_queue<int> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;
2. 哈希表（unordered_map / unordered_set）
- 用于快速查找 + 统计频次
- 注意冲突风险与哈希函数设计
3. 双端队列（deque）
- 支持双端插入删除，常用于滑动窗口
📌 三、蓝桥杯常考题型举例
| 考点 | 常见题目题型 |
|---|---|
| 单调栈 | 柱状图最大矩形、每日温度 |
| 单调队列 | 滑动窗口最大值 |
| 并查集 | 朋友圈数量、冗余连接 |
| 树状数组 | 求逆序对数、动态前缀和 |
| 线段树 | 区间最小值/最大值查询 |
| 哈希 + 数组 | 两数之和、子串查找 |
📚 四、学习建议
- 每个结构写出模板，熟悉基本操作时间复杂度。
- 刷相关题目练习：Leetcode、蓝桥OJ、洛谷（题单）
- 注意比赛时优先用 STL 提高效率。
下面我将按照蓝桥杯常考的进阶数据结构分类，列出典型的历年真题、题目链接、题意简述和高效解法解析，方便你针对性练习和掌握。
✅ 单调栈
💡 真题 1：《括号序列最大值》
- 年份：蓝桥杯国赛 2021 C++ B组
- 题意简述：给定一个合法括号序列，删除一段连续子序列后剩下部分仍为合法，求最大合法括号长度。
- 解法思路：使用单调栈求解括号匹配，记录匹配区间长度，统计最大连续合法区间。
📎 练习链接：洛谷 P2921 括号序列最大值
✅ 单调队列
💡 真题 2：《滑动窗口最大值》
- 年份：蓝桥杯模拟题，亦为经典题型
- 题意简述：给定长度为 n 的数组和窗口大小 k，输出每个窗口中的最大值。
- 解法思路：使用单调队列，保证队列中元素从大到小，队首即为最大值。
📎 练习链接：AcWing 154. 滑动窗口
✅ 并查集
💡 真题 3：《通信网络》
- 年份：蓝桥杯省赛 2019
- 题意简述：一个网络有多台主机，判断任意两台主机间是否连通。
- 解法思路：典型并查集应用。初始化并查集，合并通信对，最后检查连通性。
📎 练习链接：洛谷 P3367 并查集模板题
✅ 树状数组（Fenwick Tree）
💡 真题 4：《逆序对统计》
- 年份：蓝桥杯练习题
- 题意简述：统计一个数组中所有逆序对的个数。
- 解法思路：使用树状数组进行统计，先离散化，然后从右向左插入 + 查询前缀和。
📎 练习链接：AcWing 788. 逆序对的数量
✅ 线段树
💡 真题 5：《区间最大和》
- 年份：蓝桥杯模拟题
- 题意简述：支持区间修改和区间最大子段和查询。
- 解法思路：线段树维护多个信息（总和、前缀和、后缀和、最大字段和），合并节点时更新状态。
📎 练习链接：洛谷 P4513 小白逛公园
✅ 哈希表/位运算
💡 真题 6：《异或和最大值》
- 年份：蓝桥杯省赛 2020
- 题意简述：给定数组，求所有子数组中异或和的最大值。
- 解法思路：前缀异或 + Trie 树优化查找最大异或值。
📎 练习链接：AcWing 143. 最大异或对
✅ 双端队列
💡 真题 7：《滑动窗口均值》
- 年份：蓝桥杯 C++ A/B组模考题
- 题意简述：支持序列两端插入与删除，并实时输出窗口中值的均值。
- 解法思路：用双端队列 + 多重集合维护窗口。
📎 练习链接：洛谷 P1886 滑动窗口 / 单调队列
✅ 综合题：堆 + 并查集 + 离线查询
💡 真题 8：《信息传递》
- 年份：蓝桥杯省赛 2013
- 题意简述：每个人只会给一个人传递信息，形成链或环，求最短传递周期。
- 解法思路：图 + 并查集找环，统计最小环长度。
📎 练习链接：洛谷 P1330 信息传递
📘 总结与建议
| 数据结构 | 练题建议平台 | 推荐题目数量 |
|---|---|---|
| 单调栈/队列 | AcWing、洛谷 | 3~5道/类型 |
| 并查集 | 洛谷、蓝桥OJ | 5~8道 |
| 树状数组 | AcWing、力扣 | 5道起 |
| 线段树 | AcWing、牛客竞赛专区 | 5~10道 |
| 哈希表 | Leetcode、蓝桥模拟题 | 多刷经典题 |
| Trie树 | 衍生于哈希（难度提升） | 适当接触 |
发表回复