*算法中的数据结构(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 树⼜叫字典树或前缀树，是⼀种能够快速插⼊和查询字符串的数据结构。它利⽤字符串的公共前缀，将字符串组织成⼀棵树形结构，从⽽⼤⼤提⾼了存储以及查找效率。 字典树作用： • 查询某个单词是否出现过，并且出现⼏次； • 查询有多少个单词是以某个字符串为前缀； • 查询所有以某个前缀开头的单词；（这个作⽤可以⽤到输⼊法中，输⼊拼⾳的时候，可以提⽰可能 的单词）