*算法中的数据结构(3)

持续更新···

1.单调栈

它依旧是⼀个栈结构，只不过⾥⾯存储的数据是递增或者递减的。

2. 单调栈解决的问题
*寻找当前元素左侧，离它最近，并且⽐它⼤的元素在哪；
• 寻找当前元素左侧，离它最近，并且⽐它⼩的元素在哪；
• 寻找当前元素右侧，离它最近，并且⽐它⼤的元素在哪；
• 寻找当前元素右侧，离它最近，并且⽐它⼩的元素在哪。

寻找当前元素左侧，离它最近，并且比它大的元素在哪

从左往右遍历元素，构造⼀个单调递减的栈。插⼊当前位置的元素的时：

• 如果栈为空，则左侧不存在⽐当前元素⼤的元素；

• 如果栈⾮空，插⼊当前位置元素时的栈顶元素就是所找的元素。

注意，因为我们要找的是最终结果的位置。因此，栈⾥⾯存的是每个元素的下标。

2.单调队列

这⾥的队列和普通的队列不⼀样，是⼀个双端队列

2. 单调队列解决的问题
⼀般⽤于解决滑动窗⼝内最⼤值最⼩值问题，以及优化动态规划。

【题⽬描述】

有⼀个⻓为n 的序列a ，以及⼀个⼤⼩为k 的窗⼝。现在这个从左边开始向右滑动，每次滑动⼀

个单位，求出每次滑动后窗⼝中的最⼤值和最⼩值。

【输⼊描述】

输⼊⼀共有两⾏，第⼀⾏有两个正整数 n , k 。 第⼆⾏ n 个整数，表⽰序列 a

【输出描述】

输出共两⾏，第⼀⾏为每次窗⼝滑动的最⼩值

第⼆⾏为每次窗⼝滑动的最⼤值

窗⼝内最⼤值：

从左往右遍历元素，维护⼀个单调递减的队列：

• 当前元素进队之后，注意维护队列内的元素在⼤⼩为 k 的窗⼝内；

• 此时队头元素就是最⼤值。

3.并查集

在实现并查集的时，我们⼀般让根节点⾃⼰指向⾃⼰

在有些问题中，我们需要维护若⼲个集合，并且基于这些集合要频繁执⾏下⾯的操作：

• 查询操作：查找元素x 属于哪⼀个集合。⼀般会在每个集合中选取⼀个元素作为代表，查询的是

这个集合中的代表元素；

• 合并操作：将元素 x所在的集合与元素 y所在的集合合并成⼀个集合；（注意，合并的是元素所

在的集合，不是这两个元素！）

• 判断操作：判断元素 x 和 y 是否在同⼀个集合。

并查集（Union Find）：是⼀种⽤于维护元素所属集合 的数据结构，实现为⼀个森林，其中每棵树表 ⽰⼀个集合，树中的节点表⽰对应集合中的元素，根节点来代表整个集合。

4.扩展域并查集

将每个元素拆分成多个域，每个域代表⼀种状态或者关系。

通过维护这些域之间的关系，来处理复杂的约束条件。

敌⼈朋友问题中，我们会将 x 分成两个域，朋友域 x 以及敌⼈域 y ：

• x 和 y 是朋友，正常处理，把 x 和 y 合并成⼀个集合；

• x 和y 是敌⼈：那么 x和y 的敌⼈y+n 就是朋友，合并 x与y+n ；y 和x 的敌⼈x+n

就是朋友，合并 y与x+n 。

这样就可以利⽤两个域，将所有的关系维护起来。

【问题：食物链】

针对 x ，扩展三个域：同类域 x，捕⻝域 x + n，被捕⻝域 x + n + n。

如果 x 和 y 是同类：

• x 和 y 是同类

• x + n 与 y + n 是同类

• x + n + n 与 y + n + n 是同类

如果 x 捕⻝ y：

• x + n 与 y 同类

• x 与 y + n + n 同类

• x + n + n 与 y + n 同类

5.带权并查集

带权并查集在普通并查集的基础上，为每个结点增加了⼀个权值。这个权值可以表⽰当前结点与⽗结点之间的关系、距离或其他信息（注意，由于我们有路径压缩操作，所以最终这个权值表⽰的是当前结点相对于根结点的信息）。有了这样⼀个权值，就可以推断出集合中各个元素之间的相互关系。

 【问题：食物链】

把真话⾥⾯的相互关系，⽤"带权并查集"维护起来，权值表⽰当前节点相对于根节点的距离。那么对于集合中的任意两点 x 和 y ：

• 如果 ( d [ y ] − d [ x ]) % 3 == 0 ，表⽰两者是同类关系；

• 如果 ( d [ y ] − d [ x ]) % 3 == 1 ，表⽰两者是捕⻝关系；

• 如果 ( d [ y ] − d [ x ]) % 3 == 2 ，表⽰两者是天敌关系。

find 操作：

• 更新 d 数组：按照最基础的距离更新的⽅式， d[x] = d[x] + d[fa[x]] ；

union 操作：

• 如果 x 和 y 是同类，那么边权就是 0 ；

• 如果 x 吃 y ，那么边权就是 1 ；

6.字符串哈希

定义⼀个把字符串映射到整数的函数 ，这就是字符串哈希。就是将⼀个字符串⽤⼀个整数表示。

单次计算⼀个字符串的哈希值复杂度是O ( N ) 。如果需要多次询问⼀个字符串的⼦串的哈希值，每次重新计算效率⾮常低下。

⼀般利⽤前缀和思想先预处理字符串中每个前缀的哈希值，这样的话每次就能快速求出⼦串的哈希

了。

7.tree树

Trie 树⼜叫字典树或前缀树，是⼀种能够快速插⼊和查询字符串的数据结构。它利⽤字符串的公共前缀，将字符串组织成⼀棵树形结构，从⽽⼤⼤提⾼了存储以及查找效率。

字典树作用：
• 查询某个单词是否出现过，并且出现⼏次；
• 查询有多少个单词是以某个字符串为前缀；
• 查询所有以某个前缀开头的单词；（这个作⽤可以⽤到输⼊法中，输⼊拼⾳的时候，可以提⽰可能
的单词）