在上一篇文章 算法模式：广度优先搜索 介绍了介绍一种即适用于树，又适用于图的的算法模式。本篇文章，继续介绍一种即适用于树，又适用于图的的算法模式：深度优先搜索。
深度优先搜索 深度优先搜索主要思路是从图中一个未访问的顶点 V 开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
树是图的一种特例(连通无环的图就是树)，所以，深度优先搜索也适用于树。
在对树做深度优先搜索时，可以用递归（或显式栈，如果你想用迭代方式的话）来记录遍历过程中访问过的父节点。运行方式是从根节点开始，如果该节点不是叶子节点，我们需要干三件事：
需要区别我们是先处理根节点（pre-order，前序），处理孩子节点之间处理根节点（in-order，中序），还是处理完所有孩子再处理根节点（post-order，后序）。
递归处理当前节点的左右孩子。
LeetCode 124. 二叉树中的最大路径和 LeetCode - 124. 二叉树中的最大路径和 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例 1：
1 / \ 2 3 输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6 示例 2：
-10 / \ 9 20 / \ 15 7 输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
在上一篇文章 算法模式：多路归并 介绍了一种利用堆做链表合并的算法模式。本篇文章，介绍一种即适用于树，又适用于图的的算法模式：广度优先搜索。
广度优先搜索 广度优先搜索既适用于树，又适用于图。除此之外，在处理一些矩阵问题时，也会用到广度优先搜索的思想。当然，也可以把矩阵按照图来理解。
树上的广度优先搜索模式是通过把根节点加到队列中，然后不断遍历直到队列为空。每一次循环中，我们都会把队头结点拿出来（remove），然后对其进行必要的操作。在删除每个节点的同时，其孩子节点，都会被加到队列中。借助于队列数据结构，从而能保证树的节点按照他们的层数打印出来。打印完当前层所有元素，才能执行到下一层。所有这种需要遍历树且需要一层一层遍历的问题，都能用这种模式高效解决。
识别树上的广度优先搜索：
如果你被问到去遍历树，需要按层操作的方式（也称作层序遍历）
LeetCode 102. 二叉树的层序遍历 LeetCode - 102. 二叉树的层序遍历 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]] 示例 2：
输入：root = [1] 输出：[[1]] 示例 3：
输入：root = [] 输出：[] 提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
思路分析 思路与上述描述类似，这里直接看图：
图 1. 广度优先搜索 代码如下：
/** * @author D瓜哥 · https://www.diguage.com * @since 2025-03-31 07:31:39 */ public List<List<Integer>> levelOrder(TreeNode root) { if (root == null) { return Collections.emptyList(); } List<List<Integer>> result = new LinkedList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> level = new ArrayList<>(size); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); // 将下一层节点，从左到右，依次加入到队列中 if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } result.add(level); } return result; }
在上一篇文章 算法模式：双堆 介绍了一种利用两个堆选择中间数的算法模式。本篇文章，再来介绍一种关于堆的模式：多路归并。
多路归并 多路归并能帮咱们解决那些涉及到多组排好序的数组的问题。
每当你的输入是 K 个排好序的数组，你就可以用堆来高效顺序遍历其中所有数组的所有元素。你可以将每个数组中最小的一个元素加入到最小堆中，从而得到全局最小值。当我们拿到这个全局最小值之后，再从该元素所在的数组里取出其后面紧挨着的元素，加入堆。如此往复直到处理完所有的元素。
该模式是这样的运行的：
把每个数组中的第一个元素都加入最小堆中
取出堆顶元素（全局最小），将该元素放入排好序的结果集合里面
将刚取出的元素所在的数组里面的下一个元素加入堆
重复步骤 2，3，直到处理完所有数字
识别K路归并：
该问题的输入是排好序的数组，链表或是矩阵
如果问题让咱们合并多个排好序的集合，或是需要找这些集合中最小的元素
LeetCode 23. 合并 K 个升序链表 LeetCode - 23. 合并 K 个升序链表 给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2：
输入：lists = [] 输出：[] 示例 3：
输入：lists = [[]] 输出：[] 提示：
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] 按 升序 排列
lists[i].length 的总和不超过 104
在上一篇文章 算法模式：循环排序 介绍了一种只需 \$O(1)\$ 时间就可以完成排序的算法模式。本篇文章，来介绍一种可以快速查出数组中位数的模式：双堆。
双堆 很多问题中，我们被告知，我们拿到一大把可以分成两队的数字。为了解决这个问题，我们感兴趣的是，怎么把数字分成两半？使得：小的数字都放在一起，大的放在另外一半。双堆模式就能高效解决此类问题。
正如名字所示，该模式用到了两个堆，是不是很难猜？一个最小堆用来找最小元素；一个最大堆，拿到最大元素。这种模式将一半的元素放在最大堆中，这样你可以从这一堆中秒找到最大元素。同理，把剩下一半丢到最小堆中，\$O(1)\$ 时间找到他们中的最小元素。通过这样的方式，这一大堆元素的中位数就可以从两个堆的堆顶拿到数字，从而计算出来。
判断双堆模式的秘诀：
这种模式在优先队列，计划安排问题（Scheduling）中有奇效
如果问题让你找一组数中的最大/最小/中位数
有时候，这种模式在涉及到二叉树数据结构时也特别有用
图 1. 大堆与小堆 LeetCode 295. 数据流的中位数 LeetCode - 295. 数据流的中位数 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
示例 1：
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
在上一篇文章 算法模式：快速选择 介绍了如何利用快排思想快速选出第 K 个 最 X 的元素。本篇文章，介绍一种只需 \$O(1)\$ 时间就可以完成排序的算法模式：循环排序。
循环排序 循环排序讲述的是一直很好玩的方法：可以用来处理数组中的数值限定在一定的区间的问题。这种模式一个个遍历数组中的元素，如果当前这个数它不在其应该在的位置的话，咱们就把它和它应该在的那个位置上的数交换一下。你可以尝试将该数放到其正确的位置上，但这复杂度就会是 \$O(n^2)\$。这样的话，可能就不是最优解了。因此循环排序的优势就体现出来了。
图 1. 循环排序 循环排序适用的场景：
包含连续数字的数组（如 1 到 n 或 0 到 n-1）
需要找出缺失/重复数字的问题
需要原地排序且时间复杂度要求高的情况
LeetCode 41. 缺失的第一个正数 LeetCode - 41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 \$O(n)\$ 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。 示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。 示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。 提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
在上一篇文章 算法模式：Top K 问题 介绍了如何利用堆快速选出最 X 的 K 个元素。本篇文章，介绍一种可以快速选择第 K 个 最 X 元素的算法模式：快速选择。
快速选择 快速选择起源于快排算法。在快排算法中，把元素根据基准元素分成左右两部分，一边的元素小于基准元素，另外一个的元素大于等于基准元素，再对两边的元素递归处理，最终得到有序结果。受此启发，在将元素根据基准元素分成左右两部分后，这里假设，左边小于基准元素，右边大于等于基准元素，那么会有如下三种情况：
当前基准元素所在位置正好是 K，正好是所求结果，直接返回；
当前基准元素所在位置小于 K，那么 K 位置在当前基准元素的右边；
当前基准元素所在位置大于 K，那么 K 位置在当前基准元素的左边；
所以，该模式不仅适用于求第 K 个之最元素，也适用于求“Top K 问题”。
LeetCode 215. 数组中的第K个最大元素 LeetCode - 215. 数组中的第K个最大元素 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 \$O(n)\$ 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5 示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
在上一篇文章 算法模式：单调栈 介绍了单调栈的算法模式。本篇文章，介绍一种堆相关的算法模式：Top K 问题。（英语原文是 Top K Elements，实在没有找到好的翻译，暂时翻译成 “Top K 问题”，后续有好的翻译再改。）
Top K 问题 任何让求解最大/最小/最频繁的K个元素的题，都遵循这种模式。
用来记录这种前 K 类型的最佳数据结构就是堆了（在Java中，对应的结构是优先队列 PriorityQueue ）。这种模式借助堆来解决很多这种前 K 个数值的问题。
图 1. 大堆与小堆 这个模式是这样的：
根据题目要求，将K个元素插入到最小堆或是最大堆。
遍历剩下的还没访问的元素，如果当前出来到的这个元素比堆顶元素大或者小，那咱们把堆顶元素先删除，再加当前元素进去。
如果求最大的前 K 个元素，则适合使用小堆，将待检查元素与堆顶元素相比，堆顶元素小，直接删除堆顶元素，将待检查元素添加到堆即可。反之，则用大堆。
注意这种模式下，咱们不需要去排序数组，因为堆具有这种良好的局部有序性，这对咱们需要解决问题就够了。
识别最大 K 个元素模式：
如果你需要求最大/最小/最频繁的前K个元素
如果你需要通过排序去找一个特定的数
LeetCode 347. 前 K 个高频元素 LeetCode - 347. 前 K 个高频元素 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:
在上一篇文章 算法模式：滑动窗口 介绍了滑动窗口的算法模式。本篇文章，介绍一种堆栈相关的算法模式：单调栈。
单调栈 所谓单调栈，就是在栈的基础上，增加了一个附加条件：栈内元素单调递增或者递减，如果不符合要求，则将元素出栈，直到符合条件为止。当需要给当前的元素，找右边/左边第一个比它大/小的位置时，就特别适合使用单调栈。
图 1. 单调递增栈 图 2. 单调递减栈 一般会用到 Deque 的以下四个方法：
stack.isEmpty()：如果 deque 不包含任何元素，则返回 true，否则返回 false。因为要栈顶元素在满足要求的时候要弹出，所以需要进行空栈判断。有些场景，可能栈一定不会空的时候，就不需要该方法进行空栈判断。
stack.push(e)：将元素 e 入栈。
stack.pop()：将栈顶元素弹出，并返回当前弹出的栈顶元素。
stack.peek()：获取栈顶元素，不弹出。
// 定义一个单调栈 Deque<Integer> stack = new LinkedList<>(); // 第一个元素，直接添加 stack.push(0); // 注意：栈内存的是数组下标 for (int i = 1; i < nums.length; i++) { // 如果是单调递增栈，那么这里就是大于，即 nums[i] > nums[deque.peek()] if (nums[i] < nums[stack.peek()]) { stack.push(i); } else if (nums[i] == nums[stack.peek()]) { stack.push(i); // 此处除了入栈，在有些场景下，还有可能有其他操作 // .............. } else { // 循环比较，直到遇到当前元素小于栈顶的元素情况，跳出循环 // 单调递增栈，这里是小于，即nums[i] < nums[deque.peek()] while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) { //主要逻辑 // ............ // ............ // 弹出栈顶元素 stack.pop(); } stack.push(i); } } 记住这两句话：
单调递增栈，利用波谷剔除栈中的波峰，留下波谷；
单调递减栈，利用波峰剔除栈中的波谷，留下波峰。
LeetCode 316. 去除重复字母 LeetCode - 316. 去除重复字母 给你一个字符串 s，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc" 输出："abc" 示例 2：
输入：s = "cbacdcbc" 输出："acdb" 提示：
1 <= s.length <= 104
s 由小写英文字母组成
在上一篇文章 算法模式：双指针 介绍了双指针的算法模式。本篇文章，介绍一种类似双指针的算法模式：滑动窗口。
滑动窗口 滑动窗口类型的题目经常是用来执行数组或是链表上某个区间（窗口）上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始，一直往右边一个一个元素挪动。当然了，根据题目要求，我们可能有固定窗口大小的情况，也有窗口的大小变化的情况。
图 1. 滑动窗口 滑动窗口大概思路如下：
// 向前滑动窗口 while (right < array.lenght) { // 扩大窗口，将元素放入窗口 right++; while (缩小窗口条件) { // 处理窗口内的元素 // 缩小窗口，将元素丢出窗口 left++; } } 下面是一些我们用来判断我们可能需要上滑动窗口策略的方法：
问题的输入是一些线性结构：比如链表，数组，字符串之类的
让你去求最长/最短子字符串或是某些特定的长度要求
LeetCode 3. 无重复字符的最长子串 LeetCode - 3. 无重复字符的最长子串 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
在上一篇文章 算法模式：区间合并 介绍了合并区间所用的算法模式。本篇文章，介绍一种即可以用在数组，又可以用在链表中的算法模式：双指针。
双指针 双指针是这样的模式：两个指针朝着左右方向移动（双指针分为同向双指针和异向双指针），直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如，你需要去比较数组中每个元素和其他元素的关系时，你就需要用到双指针了。
需要双指针的原因是：如果你只用一个指针的话，你得来回跑才能在数组中找到你需要的答案。这一个指针来来回回的过程就很耗时和浪费空间了 — 这是考虑算法的复杂度分析的时候的重要概念。虽然 Brute F orce 一个指针的解法可能会奏效，但时间复杂度一般会是 \$O(n^2)\$。在很多情况下，双指针能帮助我们找到空间或是时间复杂度更低的解。
识别使用双指针的招数：
一般来说，数组或是链表是排好序的，你得在里头找一些组合满足某种限制条件
这种组合可能是一对数，三个数，或是一个子数组
LeetCode 15. 三数之和 LeetCode - 15. 三数之和 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
