数据结构进阶：单调栈、并查集与字符串哈希 | 极客日志

C++算法

数据结构进阶：单调栈、并查集与字符串哈希

数据结构进阶知识，涵盖单调栈与单调队列的应用场景及实现原理，详细讲解了并查集的基础操作、扩展域及带权并查集的处理方法，同时包含字符串哈希的前缀和思想与 Trie 树（字典树）的插入查询实现。内容涉及 C++ 代码示例，适用于算法竞赛学习。

念念不忘发布于 2026/3/29更新于 2026/4/187 浏览

数据结构进阶：单调栈、并查集与字符串哈希

概述

本文介绍基础算法篇中的数据结构进阶内容，主要包括单调栈、单调队列、并查集（含扩展域与带权）、字符串哈希以及 Trie 树。

数据结构进阶

单调栈

里面存储的是单增或者单减的栈元素。

应用：

寻找当前元素左侧，离它最近且比它大的元素位置。

寻找当前元素左侧，离它最近且比它小的元素位置。

寻找当前元素右侧，离它最近且比它大的元素位置。

寻找当前元素右侧，离它最近且比它小的元素位置。

// 寻找当前元素左侧，离它最近，并且比它大的元素在哪
int a[N]; // 已存好数据
int ret[N]; // 存答案
std::stack<int> st; // 维护一个单调递减的栈，里面存的是下标
for (int i = 1; i <= n; i++) {
    // 栈里面小于等于 a[i] 的元素全部出栈
    while (st.size() && a[st.top()] <= a[i]) st.pop();
    // 此时栈顶元素存在，栈顶元素就是所求结果
    if (st.size()) ret[i] = st.top();
    st.push(i);
}

// 寻找当前元素右侧，离它最近，并且比它大的元素在哪
// 改成 for(int i = n; i >= 1; i--) 即可

// 寻找当前元素左侧，离它最近，并且比它小的元素在哪
int a[N]; // 已存好数据
int ret[N]; // 存答案
std::stack<int> st; // 维护一个单调递增的栈，里面存的是下标
for (int i = 1; i <= n; i++) {
    // 栈里面大于等于 a[i] 的元素全部出栈
    while (st.size() && a[st.top()] >= a[i]) st.pop();
    // 此时栈顶元素存在，栈顶元素就是所求结果
     (st.()) ret[i] = st.();
    st.(i);
}

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

// 例题：洛谷 P1886 滑动窗口 /【模板】单调队列
int a[N]; // 存的元素 (已存好)
std::deque<int> q; // 存下标

// 窗口内最大值：从左往右遍历元素，维护一个单调递减的双端队列
for (int i = 1; i <= n; i++) {
    while (q.size() && a[q.back()] <= a[i]) q.pop_back();
    q.push_back(i);
    if (q.back() - q.front() + 1 > k) q.pop_front();
    if (i >= k) std::cout << a[q.front()] << " ";
}

// 窗口内最小值：从左往右遍历元素，维护一个单调递增的双端队列
// 当前元素进队之后，注意维护队列的元素在大小为 k 的窗口内
// 此时队头元素就是最小值

// 并查集的实现：例题：洛谷 P1551 亲戚
int fa[N]; // 一般并查集用 fa 来表示

// 1. 初始化：让元素自己指向自己即可
for (int i = 1; i <= n; i++) fa[i] = i;

// 2. 查询操作：就是一直向上'找爸爸'(这个 find 可以多次使用)
int find(int x) { // 查询 x 所在集合的代表元素是谁
    return fa[x] == x ? x : find(fa[x]);
}

// 3. 合并操作：(重复合并不会出错)
// 让元素 x 所在集合的代表元素指向元素 y 所在集合的代表元素
void unite(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    fa[fx] = fy;
}

// 4. 判断操作：看看两者所在集合的总代表元素是否相同
bool isSame(int x, int y) {
    return find(x) == find(y);
}

// 例题：洛谷 P1892 [BOI2003] 团伙
// 这里只写不同点：find 和 unite 与上面的写法一模一样
// 两种关系，所以 N*2：x 的母敌人是 x+n
int fa[N * 2];

// 初始化：
for (int i = 1; i <= n * 2; i++) fa[i] = i;

while (m--) { // m 是题目中的'm 个关系'
    if (op == 'F') {
        unite(x, y);
    } else {
        // 敌人，读取的是 y 和 x 是敌人关系
        // 存法：这俩都得写，少一个都不行
        unite(x, y + n); // 这两是朋友关系
        unite(y, x + n); // 这两是朋友关系
    }
}

// 带权并查集的一些操作：(这里的 d[N] 以到父结点的距离为例)
// 例题：洛谷 P1196 [NOI2002] 银河英雄传说
int d[N]; // 新加了一个 d[N]

// 1. 初始化：多初始化个 d[i] 即可
for (int i = 1; i <= n; i++) d[i] = 0;

// 2. 查询操作：(对这种代码来说，一个结点只能进行一次这种 find 操作!)
int find(int x) {
    if (fa[x] == x) return x;
    int t = find(fa[x]); // 这一步要先搞
    d[x] += d[fa[x]]; // 不为距离时可能会变为其他
    return fa[x] = t; // 完成路径压缩
}

// 3. 合并操作：x 所在集合与 y 所在集合合并，x 与 y 之间的权值是 w
void unite(int x, int y, int w) {
    int fx = find(x), fy = find(y);
    if (fx != fy) {
        fa[fx] = fy;
        d[fx] = d[y] + w - d[x]; // 可能会变，这里是拿距离举例的
    }
}

// 4. 查询操作：查询 y 与 x 之间的距离
int query(int x, int y) {
    int fx = find(x), fy = find(y);
    // 如果不在同一个集合中，说明距离未知 (具体返回什么要看题意）
    if (fx != fy) return 0x3f3f3f3f;
    return d[y] - d[x];
}

// 例题：洛谷 P10468 兔子与兔子
// 前缀字符串哈希模板：
typedef unsigned long long ULL;
const int P = 13331;
int len;
std::string s; // 一般都要搞一下 s = ' '+s; 来让 i 从 1 开始搞
ULL f[N]; // 前缀哈希数组
ULL p[N]; // 记录 P 的 i 次方 -> p[i] 为 P 的 i 次方

// 处理前缀哈希数组以及 P 的 i 次方数组
void init_hash() {
    f[0] = 0; p[0] = 1;
    for (int i = 1; i <= len; i++) {
        f[i] = f[i - 1] * P + s[i];
        p[i] = p[i - 1] * P;
    }
}

// 快速求得任意区间的哈希值
ULL get_hash(int l, int r) {
    return f[r] - f[l - 1] * p[r - l + 1];
}

// 如果题目只是简单的求单个字符串的哈希值：
ULL gethash() {
    ULL ret = 0;
    for (int i = 1; i <= len; i++) {
        ret = ret * P + s[i];
    }
    return ret;
}

// 字典树的实现：默认需要存的全是小写字母
int tree[N][26], cnt[N], e[N]; // N 一般令为所有字符串中一共有多少个字符
// cnt[i] 表示第 i 个被开辟的点被经过了多少次
// e[i] 表示以第 i 个被开辟的点为结尾的有多少个
int idx;

// 1. 准备工作
// 2. 插入字符串
void insert(std::string &s) {
    int cur = 0; // 从根节点开始
    cnt[cur]++; // 这个格子经过一次
    for (auto ch : s) {
        int path = ch - 'a'; // 这个 path 的表达式常改!!!依据题意改
        if (tree[cur][path] == 0) tree[cur][path] = ++idx;
        cur = tree[cur][path];
        cnt[cur]++;
    }
    e[cur]++;
}

// 3. 查询字符串出现的次数
int find(std::string &s) {
    int cur = 0;
    for (auto ch : s) {
        int path = ch - 'a';
        if (tree[cur][path] == 0) return 0;
        cur = tree[cur][path];
    }
    return e[cur];
}

// 4. 查询有多少个单词以字符串 s 为前缀
int find_pre(std::string &s) {
    int cur = 0;
    for (auto ch : s) {
        int path = ch - 'a';
        if (tree[cur][path] == 0) return 0;
        cur = tree[cur][path];
    }
    return cnt[cur];
}