七种核心算法解析：从并查集到Morris遍历

1. 算法工具箱：七种核心算法解析

在算法工程师的日常工作中，掌握一系列高效的核心算法就像木匠拥有趁手的工具一样重要。本文将深入剖析七种在实际工程和面试中高频出现的算法：并查集、KMP字符串匹配、Manacher算法、滑动窗口、单调栈、树形动态规划以及二叉树Morris遍历。这些算法覆盖了从数据处理到字符串处理，从线性结构到树形结构的多个关键领域。

提示：本文假设读者已经具备基础的数据结构和算法知识，如数组、链表、树等基本概念。我们将重点放在这些算法的核心思想、实现细节和实际应用上。

2. 并查集：高效处理不相交集合

2.1 并查集的核心思想

并查集（Disjoint Set Union，DSU）是一种处理不相交集合合并及查询问题的数据结构。它支持两种基本操作：

• Find：查找元素所属集合
• Union：合并两个集合

并查集的经典应用包括：

• 网络连通性问题
• 图的动态连通性判断
• 最小生成树算法（Kruskal算法）

2.2 路径压缩与按秩合并

基础并查集的实现可能会遇到性能问题。以下是两种关键优化技术：

class DSU: def __init__(self, size): self.parent = list(range(size)) self.rank = [0] * size def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # 路径压缩 return self.parent[x] def union(self, x, y): x_root = self.find(x) y_root = self.find(y) if x_root == y_root: return # 按秩合并 if self.rank[x_root] < self.rank[y_root]: self.parent[x_root] = y_root else: self.parent[y_root] = x_root if self.rank[x_root] == self.rank[y_root]: self.rank[x_root] += 1

路径压缩使查找操作的时间复杂度接近常数，而按秩合并则保证了树的平衡性。这两种优化共同作用，使得并查集的操作时间复杂度接近O(α(n))，其中α(n)是反阿克曼函数，增长极其缓慢。

2.3 实际应用案例

考虑一个社交网络中的好友关系问题：给定n个人和m对好友关系，判断任意两个人是否属于同一个朋友圈。

使用并查集的解决方案：

1. 初始化每个人为一个独立集合
2. 对于每对好友关系，合并两人的集合
3. 查询时只需比较两人的根节点是否相同

这种解决方案的时间复杂度为O(m α(n))，远优于深度优先搜索的O(n+m)解法，特别是在需要频繁查询的场景下。

3. KMP算法：高效的字符串匹配

3.1 模式匹配的痛点

传统的暴力字符串匹配算法在最坏情况下时间复杂度为O(mn)，其中m是模式串长度，n是文本串长度。KMP算法通过预处理模式串，将时间复杂度降低到O(m+n)。

3.2 部分匹配表（Partial Match Table）

KMP算法的核心是构建部分匹配表（也称为失败函数或next数组），它记录了模式串中"前缀"和"后缀"的最长公共元素长度。

def build_pmt(pattern): pmt = [0] * len(pattern) length = 0 # 当前最长公共前后缀长度 i = 1 while i < len(pattern): if pattern[i] == pattern[length]: length += 1 pmt[i] = length i += 1 else: if length != 0: length = pmt[length - 1] else: pmt[i] = 0 i += 1 return pmt

3.3 KMP搜索过程

构建好部分匹配表后，搜索过程如下：

def kmp_search(text, pattern): pmt = build_pmt(pattern) i = j = 0 # i for text, j for pattern while i < len(text): if text[i] == pattern[j]: i += 1 j += 1 if j == len(pattern): print("Pattern found at index", i - j) j = pmt[j - 1] else: if j != 0: j = pmt[j - 1] else: i += 1

注意：KMP算法虽然理论复杂度优秀，但在实际应用中，对于短模式串和随机文本，简单的暴力匹配可能更快，因为KMP的预处理和复杂逻辑会带来额外开销。

4. Manacher算法：线性时间找最长回文子串

4.1 回文串问题的挑战

寻找字符串中的最长回文子串是一个经典问题。暴力解法需要O(n³)时间，动态规划解法需要O(n²)时间，而Manacher算法将复杂度降低到了O(n)。

4.2 算法核心思想

Manacher算法的关键点在于：

1. 预处理字符串，插入特殊字符（如#）统一处理奇偶长度回文
2. 维护一个回文半径数组P，记录以每个字符为中心的最长回文半径
3. 利用对称性质避免重复计算

def manacher(s): # 预处理字符串 t = '#'.join('^{}$'.format(s)) n = len(t) P = [0] * n C = R = 0 # 中心和右边界 for i in range(1, n-1): # 利用对称性 if i < R: mirror = 2 * C - i P[i] = min(R - i, P[mirror]) # 尝试扩展 while t[i + P[i] + 1] == t[i - P[i] - 1]: P[i] += 1 # 更新中心和右边界 if i + P[i] > R: C = i R = i + P[i] # 提取最长回文子串 max_len = max(P) center = P.index(max_len) return s[(center - max_len) // 2 : (center + max_len) // 2]

4.3 算法性能分析

Manacher算法之所以能达到O(n)时间复杂度，是因为每个字符最多被比较两次：一次在扩展时，一次在更新右边界时。这使得算法非常高效，特别适合处理长字符串中的回文问题。

5. 滑动窗口：处理子数组/子串问题的利器

5.1 滑动窗口的基本概念

滑动窗口技术用于解决数组/字符串中的子区间问题，特别是需要满足某些条件的连续子序列问题。它通过维护一个窗口（通常是两个指针表示的子区间），根据条件动态调整窗口大小和位置。

5.2 两种常见模式

1. 固定大小窗口：窗口大小不变，滑动遍历整个数组
2. 可变大小窗口：窗口大小根据条件动态调整

def sliding_window_fixed(arr, k): max_sum = current_sum = sum(arr[:k]) for i in range(k, len(arr)): current_sum += arr[i] - arr[i - k] max_sum = max(max_sum, current_sum) return max_sum def sliding_window_variable(s, t): from collections import defaultdict target = defaultdict(int) for ch in t: target[ch] += 1 left = formed = 0 window = defaultdict(int) min_len = float('inf') for right, ch in enumerate(s): window[ch] += 1 if window[ch] == target[ch]: formed += 1 while formed == len(target): if right - left + 1 < min_len: min_len = right - left + 1 left_ch = s[left] window[left_ch] -= 1 if window[left_ch] < target[left_ch]: formed -= 1 left += 1 return min_len if min_len != float('inf') else 0

5.3 典型应用场景

滑动窗口技术适用于：

• 寻找满足条件的最短/最长子数组
• 计算固定大小子数组的和/平均值
• 字符串包含问题（如最小覆盖子串）
• 无重复字符的最长子串

提示：滑动窗口问题通常可以通过哈希表（记录字符频率）和双指针技术组合解决。关键在于确定何时移动窗口的左右边界。

6. 单调栈：解决Next Greater Element问题

6.1 单调栈的基本原理

单调栈是一种特殊的栈结构，它保持栈内元素单调递增或单调递减。这种结构特别适合解决"下一个更大/更小元素"这类问题。

6.2 算法实现模板

def next_greater_element(nums): stack = [] result = [-1] * len(nums) for i in range(len(nums)): while stack and nums[stack[-1]] < nums[i]: result[stack.pop()] = nums[i] stack.append(i) return result

6.3 应用场景扩展

单调栈可以解决多种变体问题：

1. 下一个更大元素（右侧）
2. 前一个更大元素（左侧）
3. 下一个更小元素
4. 每日温度问题
5. 柱状图中最大矩形

以柱状图中最大矩形问题为例：

def largest_rectangle_area(heights): stack = [-1] max_area = 0 heights.append(0) # 哨兵值 for i in range(len(heights)): while stack[-1] != -1 and heights[stack[-1]] > heights[i]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area

7. 树形动态规划：处理树结构问题

7.1 树形DP的特点

树形动态规划是指在树结构上进行的动态规划，通常采用后序遍历的方式，先处理子节点再处理父节点。这类问题通常需要考虑：

• 当前节点选或不选
• 子节点对父节点的影响
• 状态转移方程的建立

7.2 典型问题：二叉树最大路径和

class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def max_path_sum(root): max_sum = -float('inf') def helper(node): nonlocal max_sum if not node: return 0 left = max(helper(node.left), 0) right = max(helper(node.right), 0) current_sum = node.val + left + right max_sum = max(max_sum, current_sum) return node.val + max(left, right) helper(root) return max_sum

7.3 树形DP的解题模式

1. 定义递归函数：明确函数返回值的含义
2. 处理空节点：确定递归终止条件
3. 递归处理子节点
4. 计算当前节点结果
5. 更新全局最优解（如果需要）
6. 返回当前节点对父节点的贡献值

8. 二叉树Morris遍历：O(1)空间复杂度的遍历

8.1 Morris遍历的核心思想

Morris遍历利用叶子节点的空指针实现O(1)空间复杂度的二叉树遍历，无需递归或显式栈。它通过临时修改树结构（之后恢复）来实现遍历。

8.2 中序遍历实现

def morris_inorder(root): current = root while current: if not current.left: print(current.val) current = current.right else: # 找到前驱节点 predecessor = current.left while predecessor.right and predecessor.right != current: predecessor = predecessor.right if not predecessor.right: predecessor.right = current # 建立临时链接 current = current.left else: predecessor.right = None # 恢复树结构 print(current.val) current = current.right

8.3 Morris遍历的变体

Morris遍历可以稍作修改实现前序遍历：

def morris_preorder(root): current = root while current: if not current.left: print(current.val) current = current.right else: predecessor = current.left while predecessor.right and predecessor.right != current: predecessor = predecessor.right if not predecessor.right: print(current.val) # 与中序遍历的唯一区别 predecessor.right = current current = current.left else: predecessor.right = None current = current.right

注意：Morris遍历虽然节省空间，但会修改树结构（尽管最后会恢复），这在并发环境下可能会引发问题。在不需要极致空间优化的场景下，递归或迭代实现可能更合适。