Ginkgo
True love prevails.
数组模拟和 STL 两种写法都建议掌握:数组模拟更贴近竞赛底层实现,速度快、可控性高;STL 写法更简洁,日常刷题和工程代码更高效。这篇按”场景驱动”的思路整理,帮你快速定位该用什么。
一、链表:什么时候不用 vector 核心问题 vector 虽然方便,但中间插入/删除 需要移动后面所有元素,复杂度 。链表的优势在于:知道位置后,插入删除都是 。
但要注意 :链表查找第 k 个元素是 ,这点不如 vector 的 随机访问。
数组模拟单链表(竞赛常用) 为什么用数组模拟而不是指针?
避免动态内存分配的开销
内存连续,缓存友好
不会内存泄漏
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 const int N = 100010 ;int head, e[N], ne[N], idx;void init () { head = -1 ; idx = 0 ; } void add_to_head (int x) { e[idx] = x; ne[idx] = head; head = idx++; } void add (int k, int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; } void remove (int k) { ne[k] = ne[ne[k]]; }
遍历方式 :
1 2 3 for (int i = head; i != -1 ; i = ne[i]) { cout << e[i] << ' ' ; }
数组模拟双链表 场景 :需要在任意位置前后都能快速插入/删除。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 const int N = 100010 ;int e[N], l[N], r[N], idx;void init () { r[0 ] = 1 ; l[1 ] = 0 ; idx = 2 ; } void add (int k, int x) { e[idx] = x; r[idx] = r[k]; l[idx] = k; l[r[k]] = idx; r[k] = idx++; } void remove (int k) { r[l[k]] = r[k]; l[r[k]] = l[k]; }
小技巧 :要在 k 左侧插入,等价于在 l[k] 右侧插入,调用 add(l[k], x) 即可。
邻接表:存图的标配 场景 :存图,尤其是稀疏图(边数远小于 )。
核心思想 :每个点的所有出边连成一条链。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 const int N = 100010 , M = 200010 ; int h[N], e[M], ne[M], idx;void add (int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } for (int i = h[u]; i != -1 ; i = ne[i]) { int v = e[i]; }
带权图 :加一个 w[M] 数组存边权即可。
链式前向星:用数组模拟链表来存图 这部分很容易和“数组模拟链表”串起来理解:
head[u] 存点 u 的第一条边下标
Edge.next 把同一起点的边串成一条“下标链表”
遍历时从 head[u] 出发,沿 next 一直走到 -1
所以从实现角度看,链式前向星本质上就是“数组模拟链表 + 图的邻接表 ”。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 const int N = 100010 , M = 200010 ;struct Edge { int to, w, next; } edge[M]; int head[N], idx;void init () { memset (head, -1 , sizeof head); idx = 0 ; } void add (int u, int v, int w) { edge[idx] = {v, w, head[u]}; head[u] = idx++; } for (int i = head[u]; i != -1 ; i = edge[i].next) { int v = edge[i].to; int w = edge[i].w; }
二、栈与队列:受限的线性表 栈(LIFO:后进先出) 典型场景 :
表达式求值
括号匹配
DFS 递归的迭代实现
单调栈(见下文)
1 2 3 4 5 6 7 8 9 10 11 int stk[N], tt = 0 ;stk[++tt] = x; tt--; int top = stk[tt]; stack<int > stk; stk.push (x); stk.pop (); stk.top ();
队列(FIFO:先进先出) 典型场景 :
1 2 3 4 5 6 7 8 9 10 11 12 int q[N], hh = 0 , tt = -1 ;q[++tt] = x; hh++; int front = q[hh], back = q[tt];queue<int > q; q.push (x); q.pop (); q.front (); q.back ();
三、单调队列与单调栈:优化的艺术 单调队列 —— 滑动窗口最值 问题 :有一个长度为 n 的数组,和一个大小为 k 的滑动窗口,求每个窗口位置的最小值/最大值。
朴素做法 :每个窗口遍历 k 个元素,复杂度 。
单调队列优化 :维护一个”可能成为答案的候选下标”的队列,复杂度降到 。
核心直觉 :
如果一个数比后面的数大(求最小值时),它永远不可能成为答案,可以扔掉
队头超出窗口范围时,要弹出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 deque<int > q; for (int i = 0 ; i < n; i++) { if (!q.empty () && q.front () < i - k + 1 ) q.pop_front (); while (!q.empty () && a[q.back ()] >= a[i]) q.pop_back (); q.push_back (i); if (i >= k - 1 ) cout << a[q.front ()] << ' ' ; }
为什么队头就是答案 :队头是窗口内最小的元素的下标,而且是最靠左的(如果有多个相同最小值)。
单调栈 —— 找”第一个比它大/小”的数 典型问题 :
每个数左边第一个比它小的数
柱状图中最大矩形
接雨水
核心直觉 :维护一个单调栈,当前元素入栈前,把”挡路”的元素都弹掉。
1 2 3 4 5 6 7 8 9 10 11 12 13 stack<int > st; for (int i = 0 ; i < n; i++) { while (!st.empty () && a[st.top ()] >= a[i]) st.pop (); if (st.empty ()) cout << -1 << ' ' ; else cout << a[st.top ()] << ' ' ; st.push (i); }
变式 :找右边第一个比它大的数,从右往左遍历即可。
四、KMP:字符串匹配的高效算法 问题背景 给定主串 S 和模式串 P,找 P 在 S 中出现的所有位置。
暴力做法 :每个位置尝试匹配,失配后主串回退,复杂度 。
KMP 的核心 :失配时,主串不回退 ,只移动模式串。移动多少位由模式串自身的结构决定。
next 数组(或称 ne 数组) ne[i] 的含义:模式串前 i 个字符中,最长相等前后缀的长度 。
举个例子,p = "abab":
ne[1] = 0(”a”,没有真前后缀)
ne[2] = 0(”ab”,前后缀不相等)
ne[3] = 1(”aba”,前后缀都是”a”)
ne[4] = 2(”abab”,前后缀都是”ab”)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 for (int i = 2 , j = 0 ; i <= n; i++) { while (j && p[i] != p[j + 1 ]) j = ne[j]; if (p[i] == p[j + 1 ]) j++; ne[i] = j; } for (int i = 1 , j = 0 ; i <= m; i++) { while (j && s[i] != p[j + 1 ]) j = ne[j]; if (s[i] == p[j + 1 ]) j++; if (j == n) { j = ne[j]; } }
时间复杂度 : ,主串和模式串各遍历一遍。
五、Trie 树:字符串的专属数据结构 核心思想 把字符串拆成字符,按字符建一棵多叉树。从根到某个节点的路径就是一个字符串。
优势 :
前缀查询极快
统计某个字符串出现次数
找异或最大值(01 Trie)
基础模板:统计字符串出现次数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 const int N = 100010 ;int son[N][26 ], cnt[N], idx = 0 ;void insert (const string& str) { int p = 0 ; for (char ch : str) { int u = ch - 'a' ; if (!son[p][u]) son[p][u] = ++idx; p = son[p][u]; } cnt[p]++; } int query (const string& str) { int p = 0 ; for (char ch : str) { int u = ch - 'a' ; if (!son[p][u]) return 0 ; p = son[p][u]; } return cnt[p]; }
01 Trie:求最大异或对 问题 :给定 n 个数,找两个数使它们的异或值最大。
核心直觉 :异或值想最大,高位尽量变成 1 。从高位到低位贪心地走”相反位”。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 int son[N * 31 ][2 ], idx = 0 ;void insert (int x) { int p = 0 ; for (int i = 30 ; i >= 0 ; i--) { int c = (x >> i) & 1 ; if (!son[p][c]) son[p][c] = ++idx; p = son[p][c]; } } int query (int x) { int p = 0 , res = 0 ; for (int i = 30 ; i >= 0 ; i--) { int c = (x >> i) & 1 ; int rev = 1 - c; if (son[p][rev]) { res |= (1 << i); p = son[p][rev]; } else { p = son[p][c]; } } return res; }
用法 :边插入边查询,每次用当前数查询已插入的数中的最大异或值。
六、并查集:处理集合合并与查询 核心问题
典型场景 :
图的连通性
最小生成树(Kruskal)
亲戚关系传递
基础模板:路径压缩 + 按大小合并 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 struct DSU { vector<int > fa, sz; DSU (int n) { fa.resize (n + 1 ); sz.assign (n + 1 , 1 ); iota (fa.begin (), fa.end (), 0 ); } int find (int x) { return x == fa[x] ? x : fa[x] = find (fa[x]); } void unite (int x, int y) { x = find (x), y = find (y); if (x == y) return ; if (sz[x] < sz[y]) swap (x, y); fa[y] = x; sz[x] += sz[y]; } bool same (int x, int y) { return find (x) == find (y); } };
为什么按大小合并 :避免树退化成链,保证 find 的复杂度接近 (实际上是反阿克曼函数)。
扩展:维护到根的距离 场景 :不仅要判断连通性,还要知道点与点之间的关系(如”食物链”题中的捕食关系)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 struct DSUWithDist { vector<int > fa, dist; DSUWithDist (int n) { fa.resize (n + 1 ); dist.assign (n + 1 , 0 ); iota (fa.begin (), fa.end (), 0 ); } int find (int x) { if (fa[x] == x) return x; int p = fa[x]; fa[x] = find (fa[x]); dist[x] += dist[p]; return fa[x]; } };
七、堆:动态维护最值 核心能力
插入一个数
查询最值
删除最值
STL 的局限 :priority_queue 不支持删除任意元素或修改任意元素。需要这些功能时要手写堆。
手写堆模板(支持任意位置操作) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 const int N = 100010 ;int h[N], hp[N], ph[N], sz = 0 ;void heap_swap (int a, int b) { swap (ph[hp[a]], ph[hp[b]]); swap (hp[a], hp[b]); swap (h[a], h[b]); } void down (int u) { int t = u; if (u * 2 <= sz && h[u * 2 ] < h[t]) t = u * 2 ; if (u * 2 + 1 <= sz && h[u * 2 + 1 ] < h[t]) t = u * 2 + 1 ; if (u != t) { heap_swap (u, t); down (t); } } void up (int u) { while (u / 2 && h[u / 2 ] > h[u]) { heap_swap (u / 2 , u); u /= 2 ; } } h[++sz] = x; up (sz);heap_swap (1 , sz);sz--; down (1 );int pos = ph[k];heap_swap (pos, sz);sz--; down (pos);up (pos);h[ph[k]] = x; down (ph[k]);up (ph[k]);
建堆直接从 n/2 开始向前 down,因为叶子节点不用调整。
1 2 for (int i = n / 2 ; i >= 1 ; i--) down (i);
八、哈希表:O(1) 的查找 核心问题
拉链法 思路 :每个桶挂一条链表,冲突的元素串起来。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 const int MOD = 10000019 ; const int N = 200000 + 10 ;int h[MOD], e[N], ne[N], idx;void init () { memset (h, -1 , sizeof h); idx = 0 ; } void insert (int x) { int k = (x % MOD + MOD) % MOD; e[idx] = x; ne[idx] = h[k]; h[k] = idx++; } bool find (int x) { int k = (x % MOD + MOD) % MOD; for (int i = h[k]; i != -1 ; i = ne[i]) if (e[i] == x) return true ; return false ; }
开放寻址法 思路 :只开一个数组,冲突就往后找空位。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 const int MOD = 200003 ;const int NULL_VAL = 0x3f3f3f3f ;int h[MOD];void init () { memset (h, 0x3f , sizeof h); } int find_pos (int x) { int k = (x % MOD + MOD) % MOD; while (h[k] != NULL_VAL && h[k] != x) { k++; if (k == MOD) k = 0 ; } return k; }
对比 :
拉链法:稳定,装载因子可以>1
开放寻址:常数小,但装载因子高了性能下降快
九、字符串哈希:快速判断子串相等 核心思想 把字符串看成 P 进制数,计算前缀哈希。判断两段子串是否相等,只需比较哈希值。
经验取值 :
P = 131 或 13331
Q = 2^64(用 unsigned long long 自然溢出)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 using ULL = unsigned long long ;const int N = 100010 ;char str[N];ULL h[N], p[N]; ULL get (int l, int r) { return h[r] - h[l - 1 ] * p[r - l + 1 ]; } int main () { scanf ("%s" , str + 1 ); int n = strlen (str + 1 ); p[0 ] = 1 ; for (int i = 1 ; i <= n; i++) { p[i] = p[i - 1 ] * 131 ; h[i] = h[i - 1 ] * 131 + str[i]; } if (get (l1, r1) == get (l2, r2)) puts ("相等" ); }
和 KMP 的对比 :
字符串哈希:适合”子串相等判断”,写法灵活
KMP:适合”模式匹配 + 前后缀分析”,更体系化
十、STL 速记 vector 1 2 3 4 v.size (), v.empty (), v.clear () v.push_back (x), v.pop_back () v.erase (v.begin () + k) sort (v.begin (), v.end ())
string 1 2 3 s.size (), s.length (), s.c_str () s.substr (pos, len) s += "abc"
set / map 1 2 3 4 s.insert (x), s.erase (x) s.lower_bound (x) s.upper_bound (x) mp[key] = value
priority_queue 1 2 priority_queue<int > max_heap; priority_queue<int , vector<int >, greater<int >> min_heap;
常用算法 1 2 3 4 5 6 lower_bound (a.begin (), a.end (), x)upper_bound (a.begin (), a.end (), x)binary_search (a.begin (), a.end (), x)unique (a.begin (), a.end ())next_permutation (a.begin (), a.end ())__gcd(a, b)
小结:什么时候用什么
需求
推荐数据结构
随机访问 + 尾部操作
vector
中间插入/删除
链表
后进先出
栈
先进先出
队列
滑动窗口最值
单调队列
找第一个比它大/小
单调栈
字符串前缀查询
Trie
集合合并查询
并查集
动态最值
堆
O(1) 查找
哈希表
子串相等判断
字符串哈希
理解每种结构的核心优势 和代价 ,比死记模板重要得多。