Leetcode记录：全部例题直观解释与代码执行步骤
Table of contents
这篇文章是现有 Leetcode 专题的统一复习导读。原文章保留完整题目、推导和答案；这里逐题说明“为什么这样做”，并用代码注释的形式列出原答案的执行顺序。复习时先看形象理解，再按步骤回到原代码逐行阅读。
原代码索引
- 基础数据结构：二分与双指针、滑动窗口与前缀和、模拟过程、链表、哈希表 I、哈希表 II、字符串、KMP、栈与队列、单调队列。
- 排序与缓存：排序算法、缓存设计。
- 树：二叉树遍历、二叉树例题、二叉搜索树、单调栈。
- 搜索与规划：回溯、贪心、基础 DP、打家劫舍与股票、背包、序列与字符串 DP。
- 图论：并查集、DFS 与 BFS、最小生成树、Dijkstra、拓扑排序、Bellman-Ford、Floyd。
二分查找和双指针
基本二分查找
形象理解：像查字典，不从第一页开始翻，而是每次打开中间一页。目标更大就扔掉左半本，更小就扔掉右半本，每次将搜索范围缩小一半。
// 1. 用 left、right 表示当前仍可能包含答案的闭区间。
// 2. 取中点 mid，避免直接写 (left + right) 造成整数溢出。
// 3. nums[mid] 等于目标时立即返回。
// 4. 目标更大就令 left = mid + 1，否则令 right = mid - 1。
// 5. 区间为空仍未找到，返回 -1。
二分查找左右边界
形象理解：普通二分只要“撞见一个目标”就结束；边界二分像在一排相同书名中寻找最左或最右一本，找到后仍继续向对应方向挤压。
// 1. 左边界：nums[mid] >= target 时收缩右侧，逼近第一个 target。
// 2. 循环结束后检查 left 是否越界以及 nums[left] 是否真等于 target。
// 3. 右边界：nums[mid] <= target 时收缩左侧，逼近最后一个 target。
// 4. 循环结束后检查 right 的合法性，不能只返回插入位置。
两个有序数组的中位数
形象理解：不是把两副排好序的牌全部合并，而是寻找第 k 小。比较两副牌各自第 k/2 张，较小一侧的前半段肯定不可能包含第 k 小，可以整段丢弃。
// 1. 将中位数转换为求第 k 小；偶数长度时求中间两个数再取平均。
// 2. 保证较短数组耗尽时，直接从另一个数组取剩余的第 k 个。
// 3. k == 1 时返回两个当前元素中的较小值。
// 4. 比较两数组各自向后 k/2 位置的值。
// 5. 丢弃较小值所在数组的一段，并把 k 减去实际丢弃数量。
// 6. 重复直到命中边界条件。
链表的中间结点
形象理解：两个人同时沿链表走，一个每次一步，一个每次两步。快的人走到终点时，慢的人刚好走完整条路的一半。
// 1. slow 和 fast 都从头结点出发。
// 2. 每轮 slow 走一步，fast 走两步。
// 3. fast 到达末尾或越过末尾时停止。
// 4. 返回 slow；偶数长度时自然落在第二个中间结点。
删除有序数组中的重复项
形象理解：慢指针是“已整理区域的最后一个位置”，快指针像质检员向后扫描。看到新数字，就把它搬到已整理区域后面。
// 1. 慢指针指向当前最后一个不重复元素。
// 2. 快指针从第二个元素开始扫描。
// 3. 当 nums[fast] != nums[slow] 时发现新元素。
// 4. 先移动 slow，再把新元素写到 nums[slow]。
// 5. 返回 slow + 1，表示唯一元素数量。
有序数组的平方
形象理解：平方后的最大值一定来自原数组两端，因为最负的数平方后也可能最大。左右两端像两名候选人，每次把平方更大的放到答案末尾。
// 1. left 指向最左端，right 指向最右端，write 指向结果末尾。
// 2. 比较 nums[left]^2 和 nums[right]^2。
// 3. 将较大值写入 result[write]，移动对应端点。
// 4. write 从后向前移动，直到所有位置填满。
反转字符串
形象理解：像交换一排人的座位，最左和最右互换，然后向中间靠拢，直到两人相遇。
// 1. left 从开头出发，right 从末尾出发。
// 2. 交换 s[left] 和 s[right]。
// 3. left++、right--，继续处理内部区间。
// 4. left >= right 时完成原地反转。
最长回文子串
形象理解：把每个字符或两个字符之间的缝隙都当成“折纸中心”，同时向左右展开；左右字符相同就继续展开，断开时记录最大半径。
// 1. 枚举每个位置作为奇数回文中心。
// 2. 再枚举相邻位置之间作为偶数回文中心。
// 3. 左右指针在边界内且字符相同就同步向外移动。
// 4. 每次扩展成功后比较并更新最长区间。
// 5. 最后根据最佳起点和长度截取答案。
滑动窗口和前缀和
长度最小的子数组
形象理解：窗口像一根可以伸缩的尺子。右端不断向前吸收数字，和达到 target 后，左端尽量收缩，找出仍满足条件的最短尺子。
// 1. right 向右移动，并把 nums[right] 加入 windowSum。
// 2. 当 windowSum >= target 时，当前窗口是可行答案。
// 3. 更新最短长度，再移除 nums[left] 并令 left++。
// 4. 继续收缩，直到窗口重新不满足条件。
// 5. 扫描结束后，无答案返回 0。
无重复字符的最长子串
形象理解：窗口像一段只允许每种卡片出现一次的队伍。右边加入重复卡片时，从左边逐个赶人，直到重复被消除。
// 1. 右指针加入当前字符并更新出现次数或最后位置。
// 2. 若当前字符重复，移动 left 越过造成重复的旧位置。
// 3. 窗口恢复无重复后，用 right - left + 1 更新答案。
// 4. right 扫完整个字符串后返回最大长度。
最大连续 1 的个数 III
形象理解：把最多 k 次翻转看成 k 张“0 的通行证”。窗口里 0 的数量超过 k，就从左边收回通行证，直到重新合法。
// 1. right 扫描数组，遇到 0 就增加 zeroCount。
// 2. zeroCount > k 时移动 left，并在移出 0 时减少计数。
// 3. 窗口合法后更新最大长度。
// 4. 每个元素最多进出窗口一次，整体 O(n)。
最小覆盖子串
形象理解：要凑齐一张购物清单。右端不断把商品放进购物车，凑齐后左端开始退掉多余商品，直到再退一步就不完整，此时得到局部最小答案。
// 1. 统计 t 中每个字符需要的数量。
// 2. right 扩张窗口，更新窗口计数和已经满足的字符种类。
// 3. 当所有需求满足时，反复移动 left 删除多余字符。
// 4. 每次收缩前记录更短的合法窗口。
// 5. 若从未合法返回空串，否则截取最佳区间。
水果成篮
形象理解：只有两个篮子，每个篮子只能装一种水果。走过果树时出现第三种水果，就从最左边开始丢弃，直到篮子里重新只剩两种。
// 1. right 加入水果类型并增加频数。
// 2. 类型数超过 2 时，left 逐个移出水果。
// 3. 某类型频数降为 0 时从哈希表删除。
// 4. 每次窗口合法后更新最大长度。
找出所有字母异位词
形象理解：用一张 26 格的“欠账表”比较固定长度窗口和目标串。窗口每向右滑一格，只需处理离开的字符和新进入的字符，不必重新清点全部字符。
// 1. 统计 p 的字符频数，并建立同长度初始窗口。
// 2. 用 differ 记录频数不相等的字符种类数。
// 3. differ == 0 时记录窗口起点。
// 4. 窗口右移时先移出左字符，再加入右字符。
// 5. 每次修改频数前后更新 differ。
串联所有单词的子串
形象理解：字符变成等长积木。按单词长度对字符串切片，共有 wordLength 种起始偏移；每种偏移上都运行一次“单词版异位词窗口”。
// 1. 统计 words 中每个单词需要的次数。
// 2. 枚举 0 到 wordLength - 1 的切分偏移。
// 3. right 每次跨过一个完整单词，并加入窗口计数。
// 4. 某单词超量时，left 也按单词长度收缩。
// 5. 窗口单词数等于 words.size() 时记录起点。
字符串的排列
形象理解：与异位词题相同，只是不需要收集所有位置；固定长度窗口的字符账本一旦与 s1 完全一致，就可以立即返回 true。
// 1. 统计 s1 的频数，建立 s2 的固定长度窗口。
// 2. 每次滑动只更新进入和离开的两个字符。
// 3. 两份频数一致时立即返回 true。
// 4. 所有窗口都不匹配则返回 false。
除自身以外数组的乘积
形象理解：每个位置的答案由“左边所有人的乘积”和“右边所有人的乘积”拼成。先从左向右发左侧成绩，再从右向左乘上右侧成绩。
// 1. 第一遍令 answer[i] 保存 nums[0..i-1] 的乘积。
// 2. 用 rightProduct 从数组末尾向前累乘。
// 3. answer[i] *= rightProduct，得到除自身外的完整乘积。
// 4. 再把 nums[i] 纳入 rightProduct，供更左位置使用。
和为 K 的子数组
形象理解：当前前缀和是 pre，要让某段和为 k，只需在过去找前缀和 pre-k。哈希表像一本账簿，记录每种历史余额出现过几次。
// 1. 先记录前缀和 0 出现一次，表示子数组可从下标 0 开始。
// 2. 遍历元素并更新当前前缀和 pre。
// 3. 将历史中 pre - k 的出现次数累加到答案。
// 4. 最后增加 pre 的出现次数，供后续位置使用。
和可被 K 整除的子数组
形象理解：两个前缀和除以 k 的余数相同，它们的差就能被 k 整除。只需要统计过去见过多少次相同余数。
// 1. 初始化余数 0 出现一次。
// 2. 更新前缀和，并计算 ((pre % k) + k) % k 处理负数。
// 3. 相同余数的历史次数就是以当前位置结尾的新答案数。
// 4. 将当前余数计入哈希表。
连续数组
形象理解：把 0 看成 -1，问题就变成找和为 0 的最长子数组。同一个前缀和再次出现，说明两次出现之间的增量为 0。
// 1. 将 1 计为 +1，将 0 计为 -1，维护前缀和。
// 2. 只保存每个前缀和第一次出现的位置。
// 3. 再次遇到相同前缀和时，用当前位置减最早位置更新长度。
// 4. 初始记录 prefix 0 位于 -1，支持答案从下标 0 开始。
模拟过程
螺旋矩阵 II
形象理解：像沿着一圈圈跑道填数字。每填完外圈，就把上、下、左、右四条边同时向内收缩一格。
// 1. 维护 top、bottom、left、right 四条尚未填充的边界。
// 2. 沿上边从左到右填充，再令 top++。
// 3. 沿右边从上到下填充，再令 right--。
// 4. 边界仍合法时，沿下边从右到左、沿左边从下到上填充。
// 5. 四条边界交错后结束，保证每个格子只填一次。
链表
删除链表元素与虚拟头结点
形象理解：虚拟头结点像在真实队伍前放一个永远不删除的领队，使删除第一个真实节点和删除中间节点使用完全相同的操作。
// 1. 创建 dummy，并令 dummy->next = head。
// 2. cur 指向待检查节点的前一个节点。
// 3. cur->next 值等于 val 时，跨过并释放该节点。
// 4. 否则 cur 向后移动一步。
// 5. 返回 dummy->next，而不是旧的 head。
设计链表
形象理解：链表类像一列可插拔车厢；虚拟头结点固定不动，size 记录真实车厢数，使每次插入和删除都先找到前驱车厢再改两根连接。
// 1. get：检查 index，再从 dummy->next 走 index 步。
// 2. addAtHead：等价于在 index 0 插入。
// 3. addAtTail：等价于在 index size 插入。
// 4. addAtIndex：找到第 index 个位置的前驱，接入新节点并增加 size。
// 5. deleteAtIndex：找到前驱，跨过目标节点，释放内存并减少 size。
反转链表
形象理解：像逐节把火车连接方向掉头。cur 拿着当前车厢，next 先保存后续车厢，再让当前车厢指回 prev。
// 1. prev 初始化为空，cur 指向原头结点。
// 2. 保存 next = cur->next，防止反转后丢失后半段。
// 3. 令 cur->next = prev，完成当前指针反向。
// 4. prev、cur 同时向前推进。
// 5. cur 为空时 prev 就是新头结点。
K 个一组反转链表
形象理解：把链表按每 k 节切成一节节车厢组。先确认凑得齐 k 节，整组掉头后再与前后组重新接轨；最后不足 k 节的部分保持原样。
// 1. dummy 指向 head，pre 指向当前待反转组的前驱。
// 2. 从 pre 向后走 k 步找 tail；不足 k 个就结束。
// 3. 保存 nextGroup = tail->next，避免断链。
// 4. 反转 [head, tail]，得到该组新的头尾。
// 5. pre 接新组头，旧组头接 nextGroup，再进入下一组。
两两交换链表节点
形象理解：每次处理相邻两节 first、second，先把前驱接到 second，再让 second 接 first，最后让 first 接回后续链表。
// 1. dummy 统一处理头部交换，prev 指向当前二元组前驱。
// 2. 确认 prev 后至少还有两个节点。
// 3. 保存 first、second 和第二个节点之后的位置。
// 4. 按 prev -> second -> first -> next 的顺序重连。
// 5. prev 移到 first，继续交换下一对。
删除链表倒数第 N 个节点
形象理解：让 fast 比 slow 领先 n 步，之后两人同速前进。fast 到终点时，slow 恰好站在待删除节点的前一位。
// 1. 使用 dummy 避免删除头结点时单独判断。
// 2. fast 先从 dummy 向前走 n + 1 步，制造间隔。
// 3. fast、slow 同时移动直到 fast 为空。
// 4. slow->next 就是倒数第 n 个节点。
// 5. 跨过并释放该节点，返回 dummy->next。
链表相交
形象理解：A 走完自己的路后去走 B，B 走完自己的路后去走 A。两人总路程都变成 A+B，若有共同尾巴就会在入口相遇。
// 1. pA、pB 分别从两个头结点出发。
// 2. pA 到空后切换到 headB，pB 到空后切换到 headA。
// 3. 两指针每轮各走一步，自动抵消长度差。
// 4. pA == pB 时返回该节点；没有交点时二者会同时为空。
环形链表入口
形象理解：快慢指针像操场上的两名跑者，有环就一定会相遇。相遇后让一人回起点，两人都改成一步一格，再次相遇的位置就是环入口。
// 1. slow 每次一步，fast 每次两步，先判断是否存在环。
// 2. fast 或 fast->next 为空说明无环。
// 3. 首次相遇后，将一个指针重置到 head。
// 4. 两指针都每次走一步。
// 5. 第二次相遇的位置就是入环节点。
哈希表与多数之和
有效的字母异位词
形象理解：给 26 个字母各开一个账户，读取 s 时存款，读取 t 时取款；最后所有账户都归零，才说明两串只是排列不同。
// 1. 长度不同可直接返回 false。
// 2. 遍历 s，增加对应字符频数。
// 3. 遍历 t，减少对应字符频数。
// 4. 检查所有频数是否为 0。
两个数组的交集
形象理解：先把第一个数组的元素登记成会员名单，再扫描第二个数组；查到会员就加入答案集合，集合天然负责去重。
// 1. 将 nums1 放入 unordered_set。
// 2. 遍历 nums2，检查元素是否在集合中。
// 3. 命中时加入结果集合，避免重复答案。
// 4. 将结果集合转换为 vector 返回。
快乐数
形象理解：每个数字都会唯一地变成下一个数字，整个过程像沿单向道路前进；若到不了 1，就一定会进入以前走过的环。
// 1. 编写函数计算各位数字的平方和。
// 2. 用集合记录已经出现过的 n。
// 3. n == 1 时返回 true。
// 4. n 已经在集合中时说明进入循环，返回 false。
// 5. 否则记录 n，并更新为下一次平方和。
两数之和
形象理解：看到当前数字 x 时，不向后盲找，而是在过去的账本中查询它的搭档 target-x 是否已经出现。
// 1. 哈希表保存 value -> index。
// 2. 遍历 nums[i]，计算 complement = target - nums[i]。
// 3. complement 已存在时返回两个下标。
// 4. 否则记录 nums[i] 和 i，供后续元素匹配。
四数相加 II
形象理解：把四重循环拆成两支两人队伍。先统计 A+B 的所有成绩，再让 C+D 查询需要多少个相反成绩才能凑成 0。
// 1. 双循环枚举 nums1 和 nums2 的和并统计次数。
// 2. 双循环枚举 nums3 和 nums4 的和 sum。
// 3. 查找哈希表中 -sum 出现的次数。
// 4. 将该次数累加到答案。
三数之和
形象理解：排序后固定第一个数，剩下两个数像夹子从左右两端向中间夹。和太小就移动左端，太大就移动右端。
// 1. 排序，使双指针移动方向可判断，也方便去重。
// 2. 枚举第一个数 i；与前一个相同就跳过。
// 3. left=i+1、right=n-1，计算三数和。
// 4. 和小于 0 移动 left，大于 0 移动 right。
// 5. 等于 0 时记录答案，并跳过左右重复值后继续。
四数之和
形象理解：在三数之和外再固定一个数。前两层像锁定两张牌，后两张仍用左右夹逼寻找目标。
// 1. 排序并枚举第一个下标 i，跳过重复值。
// 2. 枚举第二个下标 j，同样跳过重复值。
// 3. left=j+1、right=n-1 计算四数和，使用更宽整数避免溢出。
// 4. 根据和与 target 的关系移动左右指针。
// 5. 命中后记录并跳过两端重复值。
字符串与 KMP
反转字符串 II
形象理解：把字符串按每 2k 个字符划成一组，每组只把前 k 个人掉头；最后一组人数不足时按照同样边界规则处理。
// 1. i 每次增加 2*k，定位下一组开头。
// 2. 反转区间 [i, min(i+k, n))。
// 3. 不足 k 个时 min 自动选择字符串末尾。
// 4. 后 k 个字符保持原顺序。
替换数字
形象理解：每个数字要膨胀成 number。先计算最终长度，再从后向前搬运，就不会覆盖还没读取的原字符。
// 1. 统计数字数量，计算扩展后的新长度。
// 2. resize 一次性准备最终空间。
// 3. oldIndex 从原末尾、newIndex 从新末尾向前移动。
// 4. 遇到字母复制一个字符；遇到数字倒序写入 "number"。
// 5. 两个指针完成后得到原地扩展结果。
反转字符串中的单词
形象理解：先把整句话像磁带一样整体倒放，单词顺序已经反过来；再把每个单词内部单独倒正，最后压缩多余空格。
// 1. 去除首尾和单词间多余空格，保证单词间只留一个空格。
// 2. 反转整个字符串，使单词顺序反转。
// 3. 扫描空格边界，逐个反转单词内部字符。
// 4. 返回整理后的字符串。
右旋字符串
形象理解：要把尾部 k 个字符搬到前面，可以先整体翻面，再分别把新前半段和后半段翻正，像三次翻转一副分成两摞的牌。
// 1. 令 k %= n，处理 k 大于长度的情况。
// 2. 反转整个字符串。
// 3. 反转前 k 个字符。
// 4. 反转剩余字符，得到右旋结果。
找出字符串中第一个匹配下标
形象理解：暴力算法每次不匹配都回到起点；KMP 像记住模式串自己有哪些相同前后缀，失败时直接滑到仍可能匹配的位置。
// 1. 为 needle 构造前缀表 next。
// 2. i 扫描 haystack，j 表示 needle 已匹配到的位置。
// 3. 字符不匹配时，根据 next[j] 回退 j，而不回退 i。
// 4. 字符相同就推进 j。
// 5. j 到达模式串末尾时返回起始下标。
重复的子字符串
形象理解：如果字符串由某个短模板重复组成，最长相等前后缀会留下一个完整周期；总长度必须能被周期长度整除。
// 1. 构造字符串的前缀表。
// 2. 令 longest 为最长相等真前后缀长度。
// 3. period = n - longest。
// 4. longest > 0 且 n % period == 0 时存在重复模板。
栈、队列和单调队列
用栈实现队列
形象理解：一个栈负责收件，另一个栈负责发件。发件栈为空时，把收件栈全部倒过去，两次后进先出就恢复成先进先出。
// 1. push 永远压入 input 栈。
// 2. pop/peek 前若 output 为空，将 input 全部搬到 output。
// 3. output 栈顶就是最早进入队列的元素。
// 4. 两个栈都为空时队列为空。
用队列实现栈
形象理解：新元素入队后，让它前面的所有旧元素依次出队再入队，新元素就被旋转到队首，成为栈顶。
// 1. 记录入栈前队列大小 n。
// 2. 将新元素 push 到队尾。
// 3. 重复 n 次：弹出队首并重新放到队尾。
// 4. 此时新元素位于队首，pop/top 都可直接使用。
有效的括号
形象理解：左括号像打开的盒子，必须按后开先关的顺序闭合。栈顶永远保存当前最需要被关闭的盒子。
// 1. 遇到左括号时压入对应的期望右括号。
// 2. 遇到右括号时，栈空说明没有可匹配的左括号。
// 3. 右括号不等于栈顶期望值时返回 false。
// 4. 匹配成功就弹栈；扫描结束时栈必须为空。
删除相邻重复项
形象理解：栈像一块消除游戏棋盘。新字符与栈顶相同就一起消失，否则留下成为新的栈顶。
// 1. 从左到右读取字符。
// 2. 栈非空且当前字符等于栈顶时弹出栈顶。
// 3. 否则把当前字符压栈。
// 4. 最后栈中字符按原顺序组成答案。
中缀表达式转后缀表达式
形象理解：数字直接进入输出，运算符在栈中按优先级排队；括号像临时隔离墙，右括号到来时把墙内运算符全部放行。
// 1. 操作数直接写入输出序列。
// 2. 左括号压入运算符栈。
// 3. 右括号弹出运算符直到左括号，并丢弃括号。
// 4. 普通运算符先弹出栈中优先级不低于自己的运算符，再入栈。
// 5. 扫描结束后把剩余运算符全部输出。
逆波兰表达式求值
形象理解：数字先放到工作台；遇到运算符就取出最近的两个数字计算，再把结果放回工作台。
// 1. 遇到数字就转换为整数并压栈。
// 2. 遇到运算符时先弹出右操作数，再弹出左操作数。
// 3. 计算 left op right，并把结果压回栈。
// 4. 扫描结束后栈顶就是最终答案。
前 K 个高频元素
形象理解：先给每个数字计票，再用一个只保留 k 名候选人的小顶堆。堆顶是当前入围者中票数最低的人，新候选人更强时就替换他。
// 1. 哈希表统计每个数字的频率。
// 2. 将 (频率, 数字) 放入最小堆。
// 3. 堆大小超过 k 时弹出最低频元素。
// 4. 最后堆中剩下的就是前 k 高频元素。
滑动窗口最大值
形象理解：单调队列只保留仍可能成为冠军的人。新选手比队尾强时，队尾以后既更早退场又更弱，可以永久淘汰。
// 1. 队列保存下标，且对应值从队首到队尾递减。
// 2. 新元素进入前，弹出所有不大于它的队尾下标。
// 3. 弹出已经离开窗口的队首下标。
// 4. 当前队首就是窗口最大值的下标。
// 5. 每个下标最多入队出队一次，整体 O(n)。
和至少为 K 的最短子数组
形象理解：前缀和队列保存最值得作为左端点的候选人。更晚且前缀和更小的候选人同时拥有“起点更靠后、减数更小”两项优势，可以淘汰旧候选人。
// 1. 构造 long long 前缀和，避免累加溢出。
// 2. 当前前缀和减队首 >= k 时得到可行区间，更新长度并弹队首。
// 3. 当前前缀和 <= 队尾前缀和时，队尾已被当前下标支配，弹出。
// 4. 将当前下标加入队尾，保持前缀和单调递增。
排序与缓存设计
选择排序
形象理解：像每轮从未站好的队伍中选出最矮的人，把他换到当前第一个空位；左侧已排序区每轮增长一人。
// 1. i 指向当前待确定的位置。
// 2. 在 [i,n) 中扫描并记录最小元素下标 minIndex。
// 3. 交换 nums[i] 与 nums[minIndex]。
// 4. i 右移后，左侧元素已处于最终位置。
冒泡排序
形象理解：相邻两人逆序就交换，较大的数像气泡一样一步步浮到右端；每轮结束都会固定一个当前最大值。
// 1. 从左到右比较相邻元素 nums[j] 与 nums[j+1]。
// 2. 前者更大时交换，并标记本轮发生过变化。
// 3. 每轮右端已有一个最大值，下轮无需再检查它。
// 4. 某轮没有交换说明数组已经有序，可提前结束。
插入排序
形象理解：像整理手里的扑克牌。拿起一张新牌，先把所有比它大的牌向右挪一格，再把它插进腾出的空位。
// 1. 保存 key = nums[i]，左侧 [0,i) 已有序。
// 2. j 从 i-1 向左寻找插入位置。
// 3. nums[j] > key 时将 nums[j] 右移到 j+1。
// 4. 循环结束后把 key 写入 j+1。
希尔排序
形象理解：先让相距很远的元素做插入排序，快速消除大的逆序；随后逐步缩短间隔，最后用 gap=1 的插入排序收尾。
// 1. 选择初始 gap，随后不断缩小直到 1。
// 2. 对每个 gap，把相同余数位置看成一组。
// 3. 在每组内执行“间隔为 gap”的插入排序。
// 4. gap 变小时数组已接近有序，最后一轮移动量很少。
归并排序
形象理解：不断把队伍对半拆开，单人队伍天然有序；再让左右两个有序队伍比较队首，小者先进入新队伍。
// 1. 区间长度不超过 1 时递归返回。
// 2. 按 mid 把区间递归排序成左右两半。
// 3. 用两个指针分别指向左右有序段开头。
// 4. 每次把较小元素写入临时数组。
// 5. 复制任一侧剩余元素，再写回原区间。
快速排序
形象理解：选一名基准，让比它小的人站左边、比它大的人站右边；基准就到达最终位置，再分别整理两边。
// 1. 选择 pivot；随机或三数取中可降低退化风险。
// 2. partition 移动指针，把小于基准和大于基准的元素分开。
// 3. 将基准放到分界位置，或得到左右分区边界。
// 4. 递归排序左区间和右区间。
// 5. 区间为空或只有一个元素时停止。
堆排序与 priority_queue
形象理解：最大堆像一座冠军擂台，堆顶永远是最大值。把冠军换到数组末尾后缩小赛场，再让剩余元素重新决出冠军。
// 1. 从最后一个非叶子节点向前下沉，原地建立最大堆。
// 2. 交换堆顶与当前未排序区末尾，把最大值固定下来。
// 3. 缩小 heapSize，并对新堆顶执行 siftDown。
// 4. priority_queue<int> 默认最大堆，top() 读取冠军。
// 5. priority_queue<int, vector<int>, greater<int>> 是最小堆。
// 6. 求最大的 k 个元素可维护大小为 k 的最小堆，超出时 pop 最小者。
计数排序
形象理解：不比较元素，而是给每个数值准备一个计数格；清点完后按数值从小到大重复输出对应次数。
// 1. 找到最小值与最大值，确定计数数组范围。
// 2. 扫描输入，count[value-minValue]++。
// 3. 按计数下标从小到大遍历。
// 4. 某值出现 count 次，就向原数组写回 count 次。
// 5. 适合数值范围不大的整数数据。
桶排序
形象理解：先把数据按区间扔进不同桶中，桶之间天然有先后顺序；只需把每个小桶内部排好，再从左到右倒出来。
// 1. 根据数值范围和桶宽创建 buckets。
// 2. 计算每个元素的 bucketIndex 并放入对应桶。
// 3. 分别对每个桶内部排序。
// 4. 按桶下标递增顺序连接所有元素。
// 5. 数据分布较均匀时每桶很小，效率较高。
基数排序
形象理解：先按个位稳定排队，再按十位、百位排队；因为每轮排序稳定，较低位的顺序会被保留，最终得到完整数值顺序。
// 1. exp 从 1 开始，依次代表个位、十位、百位。
// 2. 按 (value/exp)%10 对当前位执行稳定计数排序。
// 3. 将本轮结果写回原数组。
// 4. exp *= 10，直到超过最大数位。
// 5. 负数需要单独映射或拆分处理。
Introsort
形象理解：它先用快速排序获得优秀的平均性能；递归过深说明分区不理想，就切换到堆排序兜底；小区间最后交给插入排序收尾。
// 1. 以快速排序开始，并设置最大递归深度约 2*log2(n)。
// 2. 分区规模较大且深度未耗尽时继续 quicksort partition。
// 3. 深度达到上限时改用 heapsort，保证 O(n log n) 最坏复杂度。
// 4. 小区间暂不深递归，最终统一用 insertion sort 整理。
// 5. 这也是常见 std::sort 实现采用的混合思想。
滑动窗口中位数
形象理解：lower 保存较小一半，upper 保存较大一半，像天平两侧；每次插入或删除后重新平衡，中间位置自然落在两个集合边界。
// 1. deque 按时间保存记录，便于从队首淘汰过期价格。
// 2. 新价格不大于 lower 最大值就放 lower，否则放 upper。
// 3. 过期时用 multiset::find 删除那个价格本身。
// 4. 调整两侧大小，使 lower 与 upper 等大或多一个。
// 5. 奇数取 lower 最大值，偶数取 lower 最大与 upper 最小的平均。
并行归并排序与快速排序
形象理解：左右子区间像两组互不干扰的工人，可以同时工作；只有归并或 partition 形成的数据依赖点需要等待。
// 并行归并：创建左右排序 task -> taskwait -> 合并两个有序区间。
// 并行快排：先完成三路 partition -> 并行排序小于区和大于区。
// 小区间低于 cutoff 时改用串行排序，避免任务调度成本超过计算。
// OpenMP 线程池控制实际线程数，递归任务数不等于线程数。
LRU 缓存
形象理解：像把最近借过的书放回书架最前面，最久没碰的书逐渐沉到末尾。哈希表负责瞬间找到书，双向链表负责瞬间调整书的位置。
// 1. get(key)：哈希表不存在就返回 -1。
// 2. 存在时读取节点值，并用 touch/splice 把节点移到链表头部。
// 3. put 已存在 key：更新值，再 touch 为最近使用。
// 4. put 新 key：在表头插入节点，并把迭代器写入哈希表。
// 5. 超容量时删除链表尾部 LRU 节点，同时从哈希表删除其 key。
LFU 缓存
形象理解：先按使用次数把书分到不同楼层，同一楼层再按最近使用排序。淘汰时去最低频楼层，拿走其中最久没用的一本。
// 1. key 表定位 value、frequency 和其在频率链表中的位置。
// 2. get 命中后将节点从频率 f 的链表移到 f+1 链表头。
// 3. 原最低频链表变空时，minFrequency++。
// 4. put 超容量时删除 minFrequency 链表尾部节点。
// 5. 新节点频率为 1，因此插入后把 minFrequency 重置为 1。
基于时间的键值存储 TimeMap
形象理解：每个 key 都有一本按时间追加的档案。查询时间 t 时要找“不晚于 t 的最后一条记录”，即第一个大于 t 的位置再向前一步。
// 1. set 把 (timestamp,value) 追加到该 key 的有序 vector。
// 2. get 先检查 key 是否存在，不存在返回空串。
// 3. 用 upper_bound 找到第一个 timestamp > target 的记录。
// 4. 迭代器位于 begin 说明没有不晚于 target 的值。
// 5. 否则 --it，返回最后一条 timestamp <= target 的 value。
带 TTL 的令牌验证系统
形象理解：哈希表是“每张门票当前有效期”，队列是“按过期时间排列的清理提醒”。续期会留下旧提醒，清理时必须核对它是否仍代表最新有效期。
// 1. generate：计算 expire=currentTime+ttl，写哈希表并追加一条过期记录。
// 2. renew 前先清理，令牌不存在说明已过期，不能续期。
// 3. 续期时覆盖哈希表中的最新 expire，并再追加新记录。
// 4. 清理队首时，只有“已到期且等于哈希表当前 expire”的记录才能删除令牌。
// 5. 若过期记录时间不等于当前 expire，它只是续期前的陈旧提醒，跳过即可。
全 O(1) 数据结构 AllOne
形象理解：每个计数值是一节车厢，同计数 key 坐在同一车厢；加一或减一只会走到相邻车厢，空车厢立即摘掉，因此首尾始终是最小和最大计数。
// 1. 双向链表按 count 递增保存 bucket，每个 bucket 内是 key 集合。
// 2. 哈希表让 key 直接定位所在 bucket。
// 3. inc/dec 只检查相邻 count±1 的桶；不存在就原地插入新桶。
// 4. key 移到新桶后，从旧桶删除；旧桶为空就从链表删除。
// 5. 链表头桶任意 key 是最小值，尾桶任意 key 是最大值。
二叉树的遍历、属性与构造
递归前序、中序和后序遍历
形象理解：递归像让每个节点都执行同一张工作单。前序是“先登记自己，再访问孩子”，中序是“左边回来后登记自己”，后序是“两个孩子都回来后再登记自己”。
// 1. 当前节点为空时直接返回，这是递归出口。
// 2. 前序：记录 root -> 递归左树 -> 递归右树。
// 3. 中序：递归左树 -> 记录 root -> 递归右树。
// 4. 后序：递归左树 -> 递归右树 -> 记录 root。
// 5. 三种写法只改变“处理当前节点”所在的位置。
迭代前序、中序和后序遍历
形象理解：递归原本由系统调用栈替你记住“下一步回到哪里”，迭代只是把这个栈拿到自己手里。中序尤其像沿左侧楼梯走到底，再逐层返回并转向右侧。
// 前序：根先入栈；弹出就记录，再先压右孩子、后压左孩子，保证左边先处理。
// 中序：当前节点一路压栈并向左；走空后弹栈记录，再转到它的右孩子。
// 后序：按“根-右-左”收集，最后整体反转为“左-右-根”。
// 每个节点只入栈、出栈一次，因此时间 O(n)，额外空间 O(h)。
统一格式迭代遍历
形象理解：栈里同时放“待访问节点”和“待执行任务”。空指针标记相当于一张便签：再次看到它时，不再展开节点，而是把紧邻的节点值写入结果。
// 1. 弹出普通节点时，按目标遍历顺序的逆序把孩子、自己和标记压栈。
// 2. “节点后跟 nullptr”表示这个节点下次出现时应被处理。
// 3. 弹出 nullptr 后，再弹出相邻节点并记录其值。
// 4. 只需调整压栈顺序，就能统一实现前序、中序和后序。
二叉树层序遍历
形象理解：像水波从树根一圈圈向外扩散。队列中当前已有的元素正好构成一层，先记住这一层人数，处理时加入的孩子留给下一轮。
// 1. 根节点入队；队列为空表示所有层都已访问。
// 2. 每轮先保存 size = queue.size()，锁定当前层节点数。
// 3. 连续弹出 size 个节点，记录值并把非空孩子入队。
// 4. 当前层结果单独加入答案，随后开始下一层。
二叉树的右视图
形象理解：站在树的右边，每一层只能看见最右侧节点。层序遍历时，每层最后一个出队的人就是答案。
// 1. 按层遍历并保存当前层节点数 size。
// 2. 依次弹出这一层节点，同时照常加入左右孩子。
// 3. 当 i == size - 1 时，记录该节点值。
// 4. 每层恰好记录一次，得到右视图。
二叉树每层的平均值
形象理解：把每一层当成一个班级，先统计总分，再除以该层人数。总和使用更宽类型，避免节点较多时溢出。
// 1. 层序遍历开始时保存本层 size。
// 2. 用 double 或 long long 累加这一层全部节点值。
// 3. 节点的孩子继续入队，供下一层使用。
// 4. 本层结束后将 sum / size 加入答案。
填充每个节点的下一个右侧节点指针
形象理解：每层节点像排成一队，处理到第二个人时，就能让前一个人的 next 指向当前人；队尾自然指向空。
// 1. 用队列逐层取出节点。
// 2. prev 保存这一层刚处理过的前一个节点。
// 3. 当前节点到来时，若 prev 非空就令 prev->next = current。
// 4. 更新 prev，并把当前节点孩子入队。
// 5. 每层最后一个节点的 next 保持 nullptr。
对称二叉树
形象理解：不是比较两棵子树相同位置，而是把它们放到镜子两侧：左边的外侧要对上右边的外侧，左边的内侧要对上右边的内侧。
// 1. 同时传入左子树和右子树的根。
// 2. 两者都空返回 true；只有一个空或值不同返回 false。
// 3. 比较 left->left 与 right->right 这对外侧节点。
// 4. 比较 left->right 与 right->left 这对内侧节点。
// 5. 两组都对称，整棵树才对称。
二叉树和 N 叉树的最大深度
形象理解：树高等于“最高孩子的身高再加自己这一层”。N 叉树只是孩子从两个变成一组，核心仍是从所有孩子中挑最大值。
// 1. 空节点深度为 0。
// 2. 二叉树分别递归计算 leftDepth 和 rightDepth。
// 3. N 叉树遍历 children，维护最大的 childDepth。
// 4. 返回 maxChildDepth + 1，把当前节点这一层算进去。
二叉树的最小深度
形象理解：最小深度必须走到真正的叶子，不能在“只有一边为空”时提前下车。单孩子节点只能沿存在的那一侧继续走。
// 1. 空节点返回 0。
// 2. 左孩子为空时，只能返回右子树深度 + 1。
// 3. 右孩子为空时，只能返回左子树深度 + 1。
// 4. 两个孩子都存在时，取二者较小值 + 1。
平衡二叉树
形象理解：每个节点都是一架天平。孩子先报告自己的高度；任何孩子已经失衡，或两侧高度差超过 1，就用 -1 一路上报故障。
// 1. 后序递归先计算左右子树高度。
// 2. 任一侧返回 -1，当前节点无需继续计算，也返回 -1。
// 3. abs(leftHeight - rightHeight) > 1 时返回 -1。
// 4. 否则返回 max(leftHeight, rightHeight) + 1。
// 5. 根节点结果不是 -1 就说明整棵树平衡。
二叉树的所有路径
形象理解：路径像旅行清单。进入节点时写下名字，走到叶子时拍照保存；回到岔路口前擦掉刚才那一站，才能复用清单探索另一条路。
// 1. 将当前节点加入 path。
// 2. 当前节点是叶子时，把 path 格式化后加入答案。
// 3. 否则分别递归存在的左、右孩子。
// 4. 每次子调用返回后 pop_back，撤销本次选择。
路径总和
形象理解：把目标和当成旅行预算，每经过一个节点就扣除节点值；只有走到叶子并且预算恰好清零，才把这条完整路线拍照保存。随后仍要返回岔路口，继续寻找其他路线。
// 1. path 先放入根节点，并从 target 中扣除根值。
// 2. 选择一个非空孩子：把孩子值加入 path，并从 remaining 中扣除。
// 3. 到达叶子且 remaining == 0 时，把 path 复制进 result。
// 4. 递归返回后把孩子值加回 remaining，并从 path 弹出。
// 5. 左右两侧都要遍历，不能找到第一条后就提前结束。
左叶子之和
形象理解：重点不是“位于左边的节点”，而是“父节点的左孩子恰好是叶子”。因此判断动作应发生在父节点处。
// 1. 当前节点为空就返回 0。
// 2. 若左孩子存在且没有任何孩子，把左孩子值加入结果。
// 3. 无论是否命中，都递归统计左右子树中的其他左叶子。
// 4. 返回当前贡献、左子树贡献和右子树贡献之和。
找树左下角的值
形象理解：层序遍历中每到新一层，第一个出队的节点就是该层最左节点；不断覆盖答案，最后留下的就是最深层最左值。
// 1. 根节点入队，逐层遍历。
// 2. 每层开始处理 i == 0 的节点时更新 answer。
// 3. 左右孩子按左后右的顺序入队。
// 4. 最后一层结束后，answer 即树的左下角值。
翻转二叉树
形象理解：给树上的每个节点都做同一个动作——交换左右孩子。交换发生在前序还是后序都可以，只要每个节点恰好处理一次。
// 1. 当前节点为空直接返回。
// 2. 交换 root->left 和 root->right。
// 3. 递归翻转交换后的左子树。
// 4. 递归翻转交换后的右子树。
// 5. 返回 root。
根据前序和中序遍历构造二叉树
形象理解：前序序列的第一个人一定是组长；在中序序列中找到组长后，左边全属于左组，右边全属于右组，再对两个小组重复这个过程。
// 1. 前序区间首元素确定根节点值。
// 2. 用哈希表在中序序列中 O(1) 找到根位置。
// 3. 中序左段长度决定前序中左子树的边界。
// 4. 按对应区间递归构造左、右子树。
// 5. 区间为空时返回 nullptr。
二叉搜索树
搜索和插入 BST
形象理解：BST 像按编号分岔的走廊：小于当前值永远向左，大于当前值永远向右。搜索沿唯一方向走；插入则在第一次遇到空房间时落座。
// 搜索：值相等返回节点；目标更小进入左树，否则进入右树。
// 插入：走到 nullptr 时创建新节点并返回给父节点连接。
// 递归返回时重新接回 root->left 或 root->right。
// BST 的有序性让每层只访问一个分支。
删除 BST 节点
形象理解：删除没有孩子或只有一个孩子的人，可以让孩子直接顶替；有两个孩子时，请右子树里最小的人接班，才能保持整棵树的排序规则。
// 1. 按目标值大小递归寻找待删节点。
// 2. 无左孩子就返回右孩子，无右孩子就返回左孩子。
// 3. 两个孩子都存在时，找到右子树最左节点（后继）。
// 4. 用后继值覆盖当前节点，再从右子树删除那个后继。
// 5. 返回当前根，让父节点接回修改后的子树。
验证 BST
形象理解：只比较节点和直接孩子不够，因为右子树深处也可能混入过小值。中序遍历 BST 应当得到严格递增序列，像检查一列已经排好序的号码。
// 1. 中序遍历先访问左子树。
// 2. 当前值必须严格大于前一个访问值。
// 3. 使用 long long 边界或可空 prev，避免 INT_MIN 特例。
// 4. 更新 prev，再验证右子树。
// 5. 任一处不递增就立即返回 false。
BST 转双向链表
形象理解：中序遍历本来就按从小到大依次“点名”。记住上一个被点名的节点，每来一个新节点就把二者双向牵手。
// 1. 中序递归访问左子树。
// 2. prev 非空时令 prev->right = current、current->left = prev。
// 3. prev 为空说明 current 是链表头，保存 head。
// 4. 更新 prev = current，再访问右子树。
// 5. 若题目要求循环链表，最后连接 head 与 tail。
BST 中的最小绝对差和众数
形象理解：中序序列已经排好序，最小差只可能出现在相邻数字之间；相同数字也会连成一段，因此众数可以像数连续车厢一样统计。
// 最小差：中序遍历时用 current - prev 更新答案，然后更新 prev。
// 众数：当前值等于 prev 就 count++，否则把 count 重置为 1。
// count 超过 maxCount 时清空旧答案并加入当前值。
// count 等于 maxCount 时追加当前值；无需额外哈希表。
二叉树与 BST 的最近公共祖先
形象理解：普通树中，一个节点若能从左右两边分别收到 p、q 的“找到”信号，它就是汇合点；BST 中则可利用大小关系，p、q 分居当前值两侧时当前节点就是分岔口。
// 普通树：root 为空或等于 p/q 就返回 root。
// 分别递归左右树；两边都非空时返回 root，否则返回非空的一边。
// BST：p、q 都小于 root 就向左，都大于 root 就向右。
// 不再同侧时，root 就是最近公共祖先。
修剪 BST
形象理解：如果当前值小于下界，它的整个左子树只会更小，可以整棵丢弃；值大于上界时同理丢弃整个右子树。
// 1. root 为空直接返回 nullptr。
// 2. root->val < low 时，只需递归修剪并返回右子树。
// 3. root->val > high 时，只需递归修剪并返回左子树。
// 4. 当前值合法时，分别修剪左右孩子并重新接回。
// 5. 返回当前 root。
BST 转累加树
形象理解：普通中序从小到大；反向中序从大到小。一路维护已经见过的所有更大值之和，当前节点加上它，就得到累加后的值。
// 1. 按“右树 -> 当前节点 -> 左树”反向中序遍历。
// 2. 先处理所有比当前值大的节点。
// 3. sum += root->val，再令 root->val = sum。
// 4. 带着更新后的 sum 继续处理左子树。
有序数组转平衡 BST
形象理解：每次选择数组中点当组长，左右人数最接近；对子区间继续选中点，树就不会偏向一侧。
// 1. 区间为空时返回 nullptr。
// 2. 取 mid = left + (right - left) / 2 创建根节点。
// 3. 用 [left, mid-1] 构造左子树。
// 4. 用 [mid+1, right] 构造右子树。
// 5. 每层规模近似减半，生成高度平衡的 BST。
单调栈
每日温度
形象理解：栈里是还在等待更暖一天的人。新温度更高时，它会连续通知栈顶那些更冷的人，并用下标差算出他们等了几天。
// 1. 栈保存尚未找到更高温度的下标，温度从栈底到栈顶递减。
// 2. 当前温度大于栈顶温度时，弹出旧下标。
// 3. answer[old] = currentIndex - old，记录等待天数。
// 4. 重复通知所有更冷下标，再把当前下标入栈。
最大二叉树
形象理解：更大的数字会吃掉左边连续比它小的节点并让它们成为左孩子；它又可能成为左侧最近更大节点的右孩子。单调栈正好维护这条父子边界。
// 1. 栈中节点值保持递减。
// 2. 当前值更大时，连续弹栈；最后弹出的节点成为当前节点左孩子。
// 3. 栈仍非空时，当前节点成为栈顶节点的右孩子。
// 4. 当前节点入栈；最终栈底是整棵树的根。
接雨水
形象理解：栈里保存还没找到右挡板的低洼地。新柱子更高时，弹出的柱子是池底，新的栈顶是左挡板，当前柱子是右挡板。
// 1. 栈保存下标，对应高度单调递减。
// 2. 当前柱更高时弹出 bottom；栈空说明没有左挡板。
// 3. width = current - left - 1。
// 4. boundedHeight = min(height[left], height[current]) - height[bottom]。
// 5. 把 width * boundedHeight 加入总水量，再继续结算更深池子。
柱状图中最大的矩形
形象理解：每根柱子都想知道自己能向左右延伸多远。遇到更矮柱子时，栈顶高柱的右边界已经确定，而弹栈后的新栈顶就是它左边第一个更矮位置。
// 1. 首尾加入高度 0 的哨兵，统一清算边界柱子。
// 2. 栈保存高度单调递增的下标。
// 3. 当前高度更小时弹出 mid，将 height[mid] 作为矩形高度。
// 4. 右边界是 current，左边界是弹栈后的 stack.top()。
// 5. width = current - left - 1，用 height[mid] * width 更新最大面积。
回溯
组合
形象理解：从一排号码中挑 k 个，路径是手里已经拿到的号码，startIndex 是下一次只能从哪里往后挑。走满 k 层就拍下一张组合照片。
// 1. path.size() == k 时，把当前组合加入答案并返回。
// 2. i 从 startIndex 开始，保证同一组数字不会换序后重复出现。
// 3. 选择 i：path.push_back(i)。
// 4. 递归下一层：backtrack(i + 1)。
// 5. 撤销选择：path.pop_back()，再尝试下一个 i。
// 6. 上界可剪枝为 n - (k - path.size()) + 1，保证剩余数字够选。
组合总和 I
形象理解：像用不同面额硬币凑金额，每种面额可反复使用。选择某个数后下一层仍从当前下标开始，而不是从下一个下标开始。
// 1. remaining == 0 时说明正好凑齐，保存 path。
// 2. remaining < 0 时说明超支，立即回退。
// 3. 从 startIndex 枚举候选数并加入 path。
// 4. 递归时仍传 i，允许再次选择 candidates[i]。
// 5. 返回后 pop_back，恢复现场并换下一个数。
组合总和 II（原记录“组合求和 III”，Leetcode 40）
形象理解：每张数字卡只能使用一次，而且相同数字卡很多。先排序，让同一层中相同的卡站在一起；同层跳过重复卡，但不同层仍可选择另一个相同值。
// 1. 先排序 candidates，便于剪枝和去重。
// 2. remaining == 0 时保存答案。
// 3. 同一层若 i > startIndex 且 candidates[i] == candidates[i-1]，跳过。
// 4. 选择 candidates[i] 后递归 i + 1，表示这张卡不能再用。
// 5. 当前数已大于 remaining 时可直接 break。
// 6. 回溯时弹出当前数。
组合总和 III（原记录“组合求和 II”，Leetcode 216）
形象理解：只能从 1 到 9 中挑 k 个不同数字凑成 n。既要控制手里卡片数量，也要控制剩余金额；任一条件不可能满足都可提前结束。
// 1. path.size() == k 时，只在 remaining == 0 时保存答案。
// 2. 从 startIndex 到 9 枚举，确保数字不重复且组合有序。
// 3. i > remaining 时，后面数字更大，直接停止本层。
// 4. 选择 i 后递归 i + 1，并令 remaining - i。
// 5. 返回后撤销 i，继续尝试下一数字。
分割回文串
形象理解：在字符串的字符缝隙中放剪刀。每次只剪下一段已经确认是回文的片段；走到字符串末尾时，桌上的所有片段就是一种合法切法。
// 1. start == s.size() 时保存当前切分方案。
// 2. end 从 start 向右枚举当前片段终点。
// 3. 若 s[start..end] 不是回文，跳过这把剪刀位置。
// 4. 是回文就加入 path，递归处理 end + 1 之后的字符串。
// 5. 返回后弹出片段，尝试更长的当前片段。
复原 IP 地址
形象理解：要在数字串中准确插入三个点，切成四段。每段必须是 0 到 255，且除了单独的 0 之外不能有前导零。
// 1. 已得到 4 段时，只有恰好用完整个字符串才保存答案。
// 2. 每段最多向后尝试 3 个字符。
// 3. 遇到前导零、非数字或数值大于 255 时停止扩展。
// 4. 合法片段加入 path，递归处理下一位置。
// 5. 返回后删除该片段，尝试另一个终点。
子集 I
形象理解：组合题只在长度达标时拍照，子集题在到达每个节点时都拍照，因为空集、一个元素、两个元素等每种长度都是答案。
// 1. 进入每层递归时先把当前 path 加入答案。
// 2. 从 startIndex 向后枚举下一元素。
// 3. 选择 nums[i] 并递归 i + 1。
// 4. 回来后弹出 nums[i]，尝试不选它而选后面的元素。
// 5. startIndex 到末尾时自然结束，无需额外终止条件。
子集 II
形象理解：与子集 I 相同，但输入中有相同卡片。排序后，同一父节点下只允许第一个相同值开分支，避免生成两棵完全相同的子树。
// 1. 先排序 nums，让重复值相邻。
// 2. 每次进入递归都保存 path。
// 3. i > startIndex 且 nums[i] == nums[i-1] 时跳过同层重复。
// 4. 选择 nums[i]，递归 i + 1，随后撤销。
// 5. 不同递归层仍可选择相同值，因此能产生 [2,2]。
递增子序列
形象理解：原数组不能排序，因为顺序本身就是题目的一部分。每一层用一张临时名单记录本层已经选过的数，避免相同值从不同下标长出重复分支。
// 1. path.size() >= 2 时保存当前递增子序列。
// 2. i 从 startIndex 向后枚举，保持原下标顺序。
// 3. nums[i] 小于 path.back() 时跳过，保证非递减。
// 4. nums[i] 已在本层 used 集合中时跳过，防止同层重复。
// 5. 标记并选择 nums[i]，递归 i + 1，返回后弹出。
全排列 I
形象理解：有 n 个座位，每层决定一个座位坐谁。used[i] 表示第 i 个人已经坐下，直到所有座位填满时记录一种排列。
// 1. path.size() == nums.size() 时保存排列。
// 2. 每层都从下标 0 开始枚举所有人。
// 3. used[i] 为 true 说明这个人已坐下，跳过。
// 4. 选择 nums[i] 并令 used[i] = true，递归下一个座位。
// 5. 返回后弹出并恢复 used[i] = false。
全排列 II
形象理解：相同数字像长相一样的人。排序后规定在同一个座位上，只有前一个相同数字已经被使用时，后一个才有资格出场，避免交换双胞胎产生重复排列。
// 1. 先排序 nums，使相同值相邻。
// 2. used[i] 为 true 时跳过已经放入 path 的元素。
// 3. i > 0、nums[i] == nums[i-1] 且 used[i-1] == false 时跳过。
// 4. 选择当前元素、标记 used、递归，再撤销两项状态。
// 5. path 长度等于 n 时保存答案。
N 皇后
形象理解：逐行摆皇后，每行只放一个。新皇后只需向上检查同列和两条斜线，因为下面的行还没有摆任何皇后。
// 1. row == n 时说明 n 行都合法放置，保存棋盘。
// 2. 枚举当前行的每一列 col。
// 3. 检查同列、左上斜线、右上斜线是否已有皇后。
// 4. 合法就把 board[row][col] 改为 'Q'，递归下一行。
// 5. 返回后恢复为 '.'，尝试当前行的下一列。
数独
形象理解：找到第一个空格，尝试放入 1 到 9；一旦后续无解就擦掉重试。找到一条完整解后立即向上返回 true，不再枚举其他分支。
// 1. 从左到右、从上到下寻找第一个 '.'。
// 2. 对字符 '1' 到 '9' 检查所在行、列和 3x3 宫格。
// 3. 合法数字写入格子，然后递归求解剩余空格。
// 4. 递归成功立即返回 true。
// 5. 失败就把格子恢复为 '.'；所有数字失败则返回 false。
重新安排行程
形象理解：机票是只能使用一次的边，机场是图节点。行程必须用完所有票，且同一机场有多个目的地时优先尝试字典序更小者。
// 1. 邻接表按字典序保存每个出发地可用的目的地及票数。
// 2. path 从 "JFK" 开始。
// 3. 从当前机场依字典序尝试一张仍有余量的机票。
// 4. 票数减一、目的地加入 path，递归下一机场。
// 5. path.size() == tickets.size() + 1 时成功；失败就恢复票数和路径。
贪心算法
分发饼干
形象理解：小饼干留给容易满足的孩子，大饼干优先尝试满足胃口最大的孩子，避免大饼干被不必要地浪费。
// 1. 将孩子胃口和饼干尺寸分别排序。
// 2. 从最大胃口孩子和最大饼干开始比较。
// 3. 饼干够大时匹配成功，两个指针都左移。
// 4. 饼干不够时只移动孩子指针，尝试胃口更小的孩子。
// 5. 匹配次数就是最多满足人数。
摆动序列
形象理解：只保留山峰和山谷，中间同坡度的点都可以删去。当前差值与上一段有效差值异号时，才真正形成一次摆动。
// 1. prevDiff 表示上一个被计入的有效坡度。
// 2. 遍历相邻元素得到 curDiff。
// 3. curDiff > 0 且 prevDiff <= 0，或 curDiff < 0 且 prevDiff >= 0 时出现峰谷。
// 4. 答案加一，并令 prevDiff = curDiff。
// 5. 平坡或同向坡不更新 prevDiff，保留更有利的端点。
最大子序和
形象理解：前面的累计和如果已经是负债，就不值得带到今天；从当前数字重新开一段一定更好。
// 1. current 表示必须以当前位置结尾的最大子数组和。
// 2. current = max(nums[i], current + nums[i])。
// 3. 前一段为负时等价于从 nums[i] 重新开始。
// 4. 每步用 current 更新全局 best。
买卖股票的最佳时机 II
形象理解：只要明天比今天贵，就把这一小段上涨收入囊中。连续上涨的每个小台阶之和，正好等于最低点买、最高点卖的总利润。
// 1. 从第二天开始计算 prices[i] - prices[i-1]。
// 2. 差值为正时加入 profit。
// 3. 差值为负或零时跳过，不做亏损交易。
// 4. 所有正收益之和就是不限交易次数的最大利润。
跳跃游戏 I
形象理解：维护目前最远能铺到哪里，像不断延长一块安全地毯。只要当前下标仍在地毯内，就能从这里继续把地毯向前铺。
// 1. cover 表示当前可到达的最远下标。
// 2. 仅遍历 i <= cover 的位置，超出部分尚不可达。
// 3. cover = max(cover, i + nums[i])。
// 4. cover >= n - 1 时立即返回 true。
// 5. 可访问位置用尽仍未覆盖终点时返回 false。
跳跃游戏 II
形象理解：一次跳跃能覆盖一段区间。扫描当前区间内的所有起跳点，计算下一跳最远能覆盖哪里；走到本层边界时才把跳数加一，类似按层 BFS。
// 1. currentEnd 表示当前跳数能到达的右边界。
// 2. nextEnd 记录扫描当前层时发现的最远位置。
// 3. 每到一个 i，更新 nextEnd = max(nextEnd, i + nums[i])。
// 4. i == currentEnd 时必须再跳一次，令 currentEnd = nextEnd。
// 5. 到达终点前停止，避免在终点多计一次。
K 次取反后最大化数组和
形象理解：绝对值大的负数翻正收益最大，因此按绝对值从大到小处理。负数都翻完后若还剩奇数次，只能翻绝对值最小的数字，损失最少。
// 1. 按绝对值从大到小排序。
// 2. 从前向后把负数翻正，每次消耗一次 k。
// 3. 若 k 仍为奇数，翻转数组中绝对值最小的最后一个元素。
// 4. 累加最终数组得到最大和。
加油站
形象理解：从某站出发后若在 j 站前油量变负，那么这段区间里的任何站作为起点都无法越过 j；可以整段跳过，从 j+1 重新开始。
// 1. total 累加所有 gas[i] - cost[i]，判断全程总体是否可行。
// 2. current 累加当前候选起点以来的剩余油量。
// 3. current < 0 时，令 start = i + 1 并把 current 清零。
// 4. 扫描结束后 total < 0 返回 -1，否则返回 start。
分发糖果
形象理解：先只听左邻居的要求，从左向右保证高分者比左边多；再只听右邻居的要求，从右向左取两种要求的较大值。
// 1. 每个孩子先分 1 颗糖。
// 2. 从左向右，ratings[i] > ratings[i-1] 时令 candy[i] = candy[i-1] + 1。
// 3. 从右向左，ratings[i] > ratings[i+1] 时更新为 max(当前值, candy[i+1]+1)。
// 4. 两遍分别满足左右约束，最后求和。
柠檬水找零
形象理解：5 元是最灵活的零钱。收到 20 元时优先用一张 10 元加一张 5 元，保留更多 5 元应对只能用 5 元组合的情况。
// 1. 收到 5 元时增加 five。
// 2. 收到 10 元时必须消耗一张 five，并增加 ten。
// 3. 收到 20 元时优先消耗 ten + five。
// 4. 没有 10 元时再消耗三张 five。
// 5. 任一步零钱不足立即返回 false。
根据身高重建队列
形象理解：高个子不受矮个子影响，所以先安排高个子。按身高从高到低处理时，把人插入下标 k，前面恰好已有 k 个不矮于他的人。
// 1. 按身高降序排序；身高相同按 k 升序排序。
// 2. 依次取出 person = [height, k]。
// 3. 将 person 插入结果队列的第 k 个位置。
// 4. 后插入的更矮者不会改变已安排高个子的 k 条件。
用最少数量的箭引爆气球
形象理解：把每个气球看成横轴上的区间。一支箭要尽量同时穿过更多区间，因此把箭放在当前重叠区域最靠右的位置，为后面的气球留下最大余地。
// 1. 按区间右端点升序排序。
// 2. 第一支箭放在第一个气球的右端点。
// 3. 下一个气球左端点 <= arrowPos 时可被同一箭射中。
// 4. 否则必须新增一支箭，并更新 arrowPos 为该气球右端点。
无重叠区间
形象理解：要保留尽可能多的会议，就总选最早结束的那场，它给后续会议留下的时间最多；删除数等于总区间数减保留数。
// 1. 按右端点升序排序区间。
// 2. 保留第一个区间并记录 end。
// 3. 当前左端点 >= end 时可以保留，并更新 end。
// 4. 否则它与已保留区间重叠，计为删除。
划分字母区间
形象理解：每个字符都拉着一根线直到它最后一次出现的位置。扫描一个片段时，遇到的新字符可能把片段右边界继续拉长；走到最远边界才能切断。
// 1. 先记录每个字符最后出现的下标。
// 2. 扫描时令 end = max(end, last[s[i]])。
// 3. 当 i == end 时，当前片段中所有字符都不会在后面出现。
// 4. 记录 end - start + 1，并令 start = i + 1。
合并区间
形象理解：区间按起点排队后，只需观察新来的区间是否碰到结果中最后一段；碰到就拉长终点，没碰到就另开一段。
// 1. 按左端点升序排序。
// 2. 结果为空或 current.left > result.back().right 时追加新区间。
// 3. 否则两段重叠，更新 result.back().right 为更大的右端点。
// 4. 扫描完成后，结果中的区间互不重叠。
单调递增的数字
形象理解：从右向左找数字下降的位置。左边数字减一后，把右侧全部改成 9，既能恢复单调，又能让结果尽可能大。
// 1. 将 n 转成字符串，从右向左扫描。
// 2. 若 digits[i-1] > digits[i]，令 digits[i-1]--。
// 3. 记录 marker = i，表示从这里向右都应变成 9。
// 4. 继续向左检查，因为减一可能制造新的下降。
// 5. 扫描后把 marker 及其右侧全部置为 '9'。
监控二叉树
形象理解：摄像头放在叶子上很浪费；让叶子先保持“未覆盖”，它的父节点就会安装摄像头，同时覆盖父、孩子和祖父。状态从下向上传递最自然。
// 1. 后序遍历，让孩子先报告状态：未覆盖、装摄像头、已覆盖。
// 2. 空节点视为已覆盖，避免在叶子上装摄像头。
// 3. 任一孩子未覆盖时，当前节点安装摄像头并增加计数。
// 4. 任一孩子有摄像头时，当前节点已覆盖。
// 5. 两个孩子都已覆盖时，当前节点暂时未覆盖，交给父节点处理。
// 6. 根最终未覆盖时还需补装一个摄像头。
动态规划基础
爬楼梯
形象理解：到第 i 级的最后一步只有两种来源：从 i-1 走一步，或从 i-2 跨两步，因此总方法数就是两条来路之和。
// 1. 定义 dp[i] 为到达第 i 级的方法数。
// 2. 初始化 dp[1] = 1、dp[2] = 2。
// 3. 对 i >= 3，计算 dp[i] = dp[i-1] + dp[i-2]。
// 4. 只依赖前两个状态时可用两个变量滚动，空间降为 O(1)。
使用最小花费爬楼梯
形象理解：站上第 i 级可以从前一级或前两级跨来，比较两条路线截至出发台阶所付的总费用，选择更便宜的一条。
// 1. dp[i] 表示到达第 i 个位置的最小费用，楼顶位置为 n。
// 2. dp[0] = dp[1] = 0，因为可以从 0 或 1 开始。
// 3. dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。
// 4. 计算到 dp[n] 即到达楼顶的最小费用。
不同路径
形象理解：机器人进入一个格子只能来自上方或左方，所以当前格子的路线数等于“从上方来的路线数 + 从左方来的路线数”。
// 1. dp[i][j] 表示到达格子 (i,j) 的路径数量。
// 2. 第一行和第一列都只有一条直线路径，初始化为 1。
// 3. 其余格子计算 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
// 4. 右下角 dp[m-1][n-1] 就是答案。
不同路径 II
形象理解：障碍格像封死的路口，到达方法数直接清零；其他格仍把上方和左方的路线汇总过来。
// 1. 起点或终点是障碍时直接返回 0。
// 2. dp[0][0] = 1，表示从起点出发的一种方式。
// 3. 扫描每格，障碍位置令 dp[i][j] = 0。
// 4. 非障碍位置累加上方与左方存在的路径数。
// 5. 返回终点状态。
整数拆分
形象理解：第一次把 i 切出一段 j，剩下的 i-j 可以选择不再拆，也可以继续按最优方式拆；两者取更大的乘积。
// 1. dp[i] 表示整数 i 拆分后可得到的最大乘积。
// 2. 初始化 dp[2] = 1。
// 3. 枚举第一段 j，比较 j*(i-j) 与 j*dp[i-j]。
// 4. 用所有 j 的最大值更新 dp[i]。
// 5. 只需枚举到 i/2 也能覆盖对称切分。
不同的二叉搜索树
形象理解：从 1 到 n 中选 i 当根后，左边 i-1 个数可组成若干左树，右边 n-i 个数可组成若干右树；左右方案可以任意配对，所以要相乘。
// 1. dp[n] 表示由 n 个有序节点构成的 BST 数量。
// 2. dp[0] = dp[1] = 1，空树也是一种组合方式。
// 3. 枚举根节点 i = 1..n。
// 4. 累加 dp[i-1] * dp[n-i]，分别代表左右子树方案数。
// 5. 自小到大计算直到 dp[n]。
打家劫舍系列
打家劫舍 I
形象理解：走到第 i 家时只有两种合法决定：不偷它，继承前一家最优值；偷它，就必须跳过前一家并加上前两家的最优值。
// 1. dp[i] 表示考虑到第 i 家能偷到的最大金额。
// 2. dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])。
// 3. dp[i] = max(dp[i-1], dp[i-2] + nums[i])。
// 4. 返回最后状态；也可用两个变量滚动保存。
打家劫舍 II
形象理解：首尾相邻意味着不能同时偷。把环拆成两个互斥场景：不考虑最后一家，或不考虑第一家，各做一次线性打家劫舍并取较大值。
// 1. 只有一家时直接返回其金额。
// 2. 对区间 [0, n-2] 运行线性打家劫舍。
// 3. 对区间 [1, n-1] 再运行一次。
// 4. 两种场景覆盖所有合法方案，返回较大值。
打家劫舍 III
形象理解：每个树节点向父亲汇报两个数字：偷我时最多拿多少、不偷我时最多拿多少。父亲根据自己的选择组合孩子的两类状态。
// 1. 后序递归返回 {notRob, rob}。
// 2. rob = node->val + left.notRob + right.notRob。
// 3. notRob = max(left.notRob, left.rob) + max(right.notRob, right.rob)。
// 4. 根节点返回后取两种状态的较大值。
股票动态规划
只能买卖一次
形象理解：每天结束只记录两种账户状态：手里有股票或没有股票。只允许一次交易时，“持有”的买入来源必须是初始现金，而不能接在上一笔卖出之后。
// 1. hold 表示当天结束持有股票的最大收益，初始化为 -prices[0]。
// 2. cash 表示当天结束不持股的最大收益，初始化为 0。
// 3. hold = max(旧 hold, -prices[i])，决定继续持有或今天首次买入。
// 4. cash = max(旧 cash, 旧 hold + prices[i])，决定不动或今天卖出。
// 5. 最终返回 cash。
可以买卖任意次
形象理解：仍是持股和空仓两个账户，但今天买入可以使用之前已经赚到的现金，因此允许一笔交易结束后再开始下一笔。
// 1. 保存更新前的 oldHold 和 oldCash，避免同一天状态串用。
// 2. hold = max(oldHold, oldCash - prices[i])。
// 3. cash = max(oldCash, oldHold + prices[i])。
// 4. 扫描所有天后，空仓状态 cash 是最大已实现利润。
最多买卖两次
形象理解：一天结束可能处于五个阶段：未操作、第一次持有、第一次卖出、第二次持有、第二次卖出。每个阶段只从自己或前一阶段转移。
// 1. buy1 = max(buy1, -price)。
// 2. sell1 = max(sell1, buy1 + price)。
// 3. buy2 = max(buy2, sell1 - price)。
// 4. sell2 = max(sell2, buy2 + price)。
// 5. 更新时注意使用上一天状态，最终返回 sell2。
最多买卖 K 次
形象理解：把两次交易的五个阶段扩展成 2k+1 个阶段，奇数编号表示第几次持有，偶数编号表示第几次卖出。
// 1. dp[j] 表示当天处于第 j 个交易阶段的最大收益。
// 2. 所有买入阶段初始化为 -prices[0]，卖出阶段初始化为 0。
// 3. 奇数 j：dp[j] = max(dp[j], dp[j-1] - price)。
// 4. 偶数 j：dp[j] = max(dp[j], dp[j-1] + price)。
// 5. 每天按阶段更新，返回最后一次卖出阶段。
含冷冻期的股票交易
形象理解：卖出后的第二天不能买，所以不能只区分持股和空仓；要单独记住“今天刚卖出”和“处于冷冻/普通空仓”的状态。
// 1. hold：持股；sold：今天刚卖出；rest：不持股且可继续等待。
// 2. newHold = max(oldHold, oldRest - price)，只能从可买状态买入。
// 3. newSold = oldHold + price，卖出必须来自昨天持股。
// 4. newRest = max(oldRest, oldSold)，冷冻一天后进入可等待状态。
// 5. 最终返回 sold 与 rest 的较大值。
含手续费的股票交易
形象理解：仍使用持股/空仓两状态，只需在买入或卖出的一侧扣一次手续费，不能两边都扣。
// 1. hold 初始化为 -prices[0]，cash 初始化为 0。
// 2. newHold = max(oldHold, oldCash - price)。
// 3. newCash = max(oldCash, oldHold + price - fee)。
// 4. 每笔完整交易只在卖出时扣一次 fee。
// 5. 返回最终 cash。
0-1 背包和完全背包
二维 0-1 背包
形象理解：每件物品像一次性卡牌。走到第 i 件时，可以不拿它，或在背包容量足够时拿它并接上“只考虑前 i-1 件”的最优值。
// 1. dp[i][j] 表示只考虑 0..i 的物品、容量 j 时的最大价值。
// 2. 不选物品 i：继承 dp[i-1][j]。
// 3. 选物品 i：dp[i-1][j-weight[i]] + value[i]。
// 4. 容量足够时取两者最大值，否则只能不选。
// 5. 初始化第一行后逐物品、逐容量计算。
一维 0-1 背包
形象理解：把二维表压成一行后，容量必须从大到小更新。这样读取的 dp[j-weight] 仍属于上一轮，保证当前物品不会在同一轮被拿多次。
// 1. dp[j] 表示容量 j 的最大价值。
// 2. 外层逐个枚举物品。
// 3. 内层 j 从 capacity 递减到 weight[i]。
// 4. dp[j] = max(dp[j], dp[j-weight[i]] + value[i])。
// 5. 倒序是“一件物品只用一次”的关键。
分割等和子集
形象理解：总和若为奇数一定无法平分；否则问题就是从数组中挑一些数，恰好装满容量为 sum/2 的 0-1 背包。
// 1. 求总和，奇数直接返回 false。
// 2. target = sum / 2。
// 3. 对每个 num，容量从 target 向 num 倒序更新。
// 4. dp[j] = max(dp[j], dp[j-num] + num)。
// 5. 最终 dp[target] == target 时可平分。
最后一块石头的重量 II
形象理解：把石头分成两堆互相碰撞，最终重量是两堆总重之差。让较轻那堆尽量接近总重一半，差值就最小。
// 1. target = total / 2，建立 0-1 背包。
// 2. 每块石头既是重量也是价值。
// 3. 容量倒序更新 dp[j] = max(dp[j], dp[j-stone] + stone)。
// 4. dp[target] 是不超过一半的最大一堆重量。
// 5. 答案为 total - 2 * dp[target]。
目标和
形象理解：设加正号的数之和为 P、加负号的数之和为 N，则 P-N=target 且 P+N=sum，所以只需统计和为 (sum+target)/2 的子集数量。
// 1. 若 abs(target) > sum 或 sum + target 为奇数，返回 0。
// 2. bag = (sum + target) / 2。
// 3. dp[0] = 1，表示什么都不选恰好组成 0 的一种方法。
// 4. 对每个 num，容量从 bag 向 num 倒序。
// 5. dp[j] += dp[j-num]，累计选择 num 后新增的方案数。
一和零
形象理解：背包有两个容量维度：最多能用 m 个 0 和 n 个 1。每个字符串是一件同时消耗两种资源、价值为 1 的物品。
// 1. 统计当前字符串的 zeroCount 和 oneCount。
// 2. dp[i][j] 表示最多使用 i 个 0、j 个 1 能选择的字符串数。
// 3. i 从 m 向 zeroCount 倒序，j 从 n 向 oneCount 倒序。
// 4. dp[i][j] = max(dp[i][j], dp[i-zero][j-one] + 1)。
// 5. 双维度都倒序，保证字符串只使用一次。
完全背包的遍历顺序
形象理解：完全背包中的物品可重复拿，所以容量从小到大更新；这样本轮刚更新的 dp[j-weight] 可以继续使用当前物品。
// 1. 外层物品、内层容量正序：统计组合，且允许当前物品重复使用。
// 2. 外层容量、内层物品：不同选择顺序会被分别统计，得到排列数。
// 3. 求最大价值时二者通常都可行；求方案数时顺序决定含义。
// 4. 0-1 背包容量倒序，完全背包容量正序，不能混淆。
零钱兑换 II
形象理解：要统计不考虑顺序的硬币组合，所以先固定硬币种类，再逐步扩充金额；同一组合不会因为拿币顺序不同被重复计算。
// 1. dp[0] = 1，组成金额 0 有一种空方案。
// 2. 外层遍历每种 coin。
// 3. 内层 amount 从 coin 正序到目标金额。
// 4. dp[amount] += dp[amount-coin]。
// 5. 返回 dp[target]，相同硬币可在本轮重复使用。
组合总和 IV
形象理解：[1,2] 和 [2,1] 算两种答案，因此先枚举目标总和，再枚举最后放入哪个数字，让不同顺序进入不同转移路径。
// 1. dp[0] = 1。
// 2. 外层 sum 从 1 正序到 target。
// 3. 内层枚举每个 num。
// 4. sum >= num 时，dp[sum] += dp[sum-num]。
// 5. 外容量、内物品使答案按排列计数。
爬楼梯作为完全背包
形象理解：若一次可走 1..m 级，每一种走法就是用这些“步长硬币”按顺序凑出楼层 n；顺序不同的步长序列算不同路线。
// 1. dp[0] = 1，站在原地是一种起始方式。
// 2. 外层枚举当前要到达的楼层 i。
// 3. 内层枚举最后一步 step = 1..m。
// 4. i >= step 时累加 dp[i-step]。
// 5. 容量在外、步长在内，因此统计排列。
零钱兑换
形象理解：每个金额都问：“如果最后使用某枚硬币，之前最少需要几枚？”从所有合法硬币给出的候选值中选最小。
// 1. dp[0] = 0，其余初始化为不可达的大值 target + 1。
// 2. 对每枚 coin，金额从 coin 向 target 正序更新。
// 3. dp[j-coin] 可达时，dp[j] = min(dp[j], dp[j-coin] + 1)。
// 4. 最终仍是大值说明无法组成，返回 -1。
完全平方数
形象理解：把 1,4,9... 这些平方数当成可无限使用的硬币，目标是用最少硬币凑成 n。
// 1. dp[0] = 0，其余初始化为大值。
// 2. 枚举平方数 square = i*i，且 square <= n。
// 3. 容量 j 从 square 正序到 n。
// 4. dp[j] = min(dp[j], dp[j-square] + 1)。
// 5. 返回 dp[n]。
单词拆分
形象理解：dp[i] 表示字符串前 i 个字符已经能被词典切好。枚举最后一个切口 j，只要前半段可达且 s[j..i) 在词典中，i 就可达。
// 1. dp[0] = true，空前缀天然可拆分。
// 2. 枚举结尾 i = 1..n。
// 3. 枚举最后切口 j = 0..i-1。
// 4. 若 dp[j] 为真且 s.substr(j, i-j) 在字典中，令 dp[i] = true 并停止。
// 5. 返回 dp[n]。
子序列与字符串动态规划
最长递增子序列
形象理解：dp[i] 只负责“必须以 nums[i] 收尾”的队伍。向前寻找所有比它小的末尾，把 nums[i] 接在其中最长的一队后面。
// 1. 每个元素单独都能组成长度 1，初始化 dp[i] = 1。
// 2. 对每个 i，枚举所有 j < i。
// 3. nums[j] < nums[i] 时，可把 i 接到 j 后面。
// 4. dp[i] = max(dp[i], dp[j] + 1)。
// 5. 答案是所有 dp[i] 的最大值，不一定在最后位置结束。
最长连续递增序列
形象理解：连续意味着不能从更早位置跳过来。当前数字比前一个大时，当前增长跑道延长一格；否则从当前位置重新起跑。
// 1. current 和 best 初始化为 1。
// 2. nums[i] > nums[i-1] 时令 current++。
// 3. 否则令 current = 1，从当前元素重新开始。
// 4. 每一步用 current 更新 best。
最长重复子数组
形象理解：把两个数组排成棋盘，元素相等时当前格能沿左上角的连续对角线延长一格；不相等则连续段立即归零。
// 1. dp[i][j] 表示以 nums1[i-1]、nums2[j-1] 结尾的相同连续段长度。
// 2. 两元素相等时 dp[i][j] = dp[i-1][j-1] + 1。
// 3. 不相等时 dp[i][j] = 0，因为子数组必须连续。
// 4. 计算过程中维护所有状态的最大值。
最长公共子序列
形象理解：两个字符串的末尾字符相同，就把它接到两个前缀的公共子序列后；末尾不同，就尝试放弃任意一边的末尾字符。
// 1. dp[i][j] 表示 text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度。
// 2. 字符相同：dp[i][j] = dp[i-1][j-1] + 1。
// 3. 字符不同：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
// 4. 第一行和第一列为空串情况，初始化为 0。
// 5. 返回 dp[m][n]。
不相交的线
形象理解：相同数字之间连线且不能相交，等价于保持两数组原顺序选择相同元素，也就是最长公共子序列。
// 1. dp[i][j] 表示两个数组前缀最多能连多少条不相交线。
// 2. nums1[i-1] == nums2[j-1] 时连接它们，接在 dp[i-1][j-1] 后。
// 3. 不相等时放弃一边当前元素，取上方与左方状态较大值。
// 4. 返回右下角状态。
动态规划版本的最大子序和
形象理解：与贪心解释一致，只是显式定义 dp[i] 为必须以 i 结尾的最大和，决定接上前一段还是从当前数重新开始。
// 1. dp[0] = nums[0]。
// 2. dp[i] = max(nums[i], dp[i-1] + nums[i])。
// 3. dp[i-1] 为负时，丢弃旧段更有利。
// 4. 返回 dp 数组中的最大值。
判断子序列
形象理解：二维 DP 版本记录 s 的前 i 个字符能否全部嵌入 t 的前 j 个字符；若当前字符不匹配，只能丢弃 t 的当前字符继续寻找。
// 1. dp[i][j] 表示 s[0..i) 是否为 t[0..j) 的子序列。
// 2. 空字符串是任何字符串的子序列，初始化 dp[0][j] = true。
// 3. 字符相等时继承 dp[i-1][j-1]。
// 4. 字符不等时继承 dp[i][j-1]，表示跳过 t[j-1]。
// 5. 返回 dp[m][n]；双指针还可把空间降到 O(1)。
不同的子序列
形象理解：计算 s 中能选出多少个 t。若当前字符相同，可以用它匹配 t 的末尾，也可以不用它；不同则只能不用它。
// 1. dp[i][j] 表示 s 前 i 个字符组成 t 前 j 个字符的方案数。
// 2. dp[i][0] = 1，因为任何前缀删除全部字符都能得到空串。
// 3. s[i-1] == t[j-1] 时：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。
// 4. 不相等时：dp[i][j] = dp[i-1][j]。
// 5. 使用足够宽的整数类型保存方案数。
两个字符串的删除操作
形象理解：先找两字符串都愿意保留的最长公共子序列，其余字符全部删除；两边删除数就是总长度减去两倍的保留长度。
// 1. 用 LCS 动态规划求 longestCommon。
// 2. word1 需要删除 word1.size() - longestCommon 个字符。
// 3. word2 同理删除 word2.size() - longestCommon 个字符。
// 4. 返回 m + n - 2 * longestCommon。
编辑距离
形象理解：让两个前缀对齐。末尾相同时不花钱；不同时考虑删除、插入、替换三种动作，选择从哪个相邻状态走一步最便宜。
// 1. dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数。
// 2. dp[i][0] = i、dp[0][j] = j。
// 3. 末尾字符相同：dp[i][j] = dp[i-1][j-1]。
// 4. 不同：取删除 dp[i-1][j]、插入 dp[i][j-1]、替换 dp[i-1][j-1] 的最小值再加 1。
// 5. 返回 dp[m][n]。
回文子串
形象理解：区间 [i,j] 是回文，需要两端字符相同，并且内部 [i+1,j-1] 已是回文；长度 1 或 2 时内部为空，可直接成立。
// 1. dp[i][j] 表示 s[i..j] 是否为回文。
// 2. i 从右向左遍历，保证 dp[i+1][j-1] 已计算。
// 3. s[i] == s[j] 且 (j-i <= 1 或 dp[i+1][j-1]) 时为真。
// 4. 每得到一个 true 就把回文子串数量加一。
最长回文子序列
形象理解：区间两端相等时，可以把它们一起包在内部最长回文两侧；不相等时，只能舍弃左端或右端并选择更长结果。
// 1. dp[i][j] 表示 s[i..j] 内最长回文子序列长度。
// 2. 单字符初始化 dp[i][i] = 1。
// 3. s[i] == s[j] 时 dp[i][j] = dp[i+1][j-1] + 2。
// 4. 否则 dp[i][j] = max(dp[i+1][j], dp[i][j-1])。
// 5. i 倒序、j 正序计算，返回 dp[0][n-1]。
正则表达式匹配
形象理解：普通字符或 . 只消费一次；* 像一个可伸缩印章，可以让前一个模式出现零次，也可以在字符匹配时再消费一次文本、但继续保留这个印章。
// 1. dp[i][j] 表示 s 前 i 个字符是否匹配 p 前 j 个字符。
// 2. dp[0][0] = true；形如 a*b* 的模式可通过“出现零次”匹配空串。
// 3. 普通字符或 '.' 匹配时，继承 dp[i-1][j-1]。
// 4. p[j-1] == '*' 时，dp[i][j] 可取 dp[i][j-2]，表示前一字符出现零次。
// 5. 若前一模式字符匹配 s[i-1]，还可取 dp[i-1][j]，表示多匹配一次。
// 6. 返回 dp[m][n]。
并查集
寻找图中是否存在路径
形象理解：并查集给每个连通块选一个代表人。每条边让两边代表人合并；最后只需看起点和终点是否拥有同一个代表人。
// 1. parent[i] = i，初始每个节点自成集合。
// 2. find(x) 沿父指针找到根，并用路径压缩让沿途节点直连根。
// 3. 对每条边执行 unite(u, v)，把两个根合并。
// 4. 比较 find(source) 与 find(destination) 是否相等。
冗余连接
形象理解：一棵树中新增一条连接同一连通块内部两点的边，就会闭合成环。扫描边时若两端代表人已相同，这条边就是多余边。
// 1. 初始化并查集。
// 2. 按输入顺序扫描边 (u,v)。
// 3. find(u) == find(v) 时，加入这条边会形成环，立即返回。
// 4. 否则 unite(u,v)，让两个连通块合并。
冗余连接 II
形象理解：有向树失效只有两类原因：某节点有两个父亲，或图中出现环。先找“双父节点”的两条候选边，再通过跳过候选边做并查集验证。
// 1. 扫描每条有向边，记录每个节点第一次出现的父边。
// 2. 若某节点收到第二条父边，保存前后两条候选边。
// 3. 优先跳过后出现的候选边，检查其余边能否构成合法树。
// 4. 若可以，后候选边就是答案；否则前候选边才是答案。
// 5. 若不存在双父节点，直接用并查集返回形成环的边。
图的遍历与岛屿问题
所有可能的路径
形象理解：从 0 号节点出发沿每条有向边试走，路径像一条面包屑轨迹；到达终点就复制轨迹，返回时擦掉最后一步去试另一条边。
// 1. path 初始化为 {0}。
// 2. 当前节点等于 n-1 时保存 path 并返回。
// 3. 枚举 graph[current] 中的每个 next。
// 4. 将 next 加入 path，递归 next。
// 5. 返回后 pop_back，恢复路径。
岛屿数量
形象理解：每发现一块尚未标记的陆地，就发现了一座新岛；从它出发把上下左右连着的陆地全部“涂掉”，同一座岛之后就不会重复计数。
// 1. 双重循环扫描网格。
// 2. 遇到 '1' 时岛屿数加一，并启动 DFS/BFS。
// 3. 搜索把当前陆地标记为已访问。
// 4. 对四个方向中仍为 '1' 的邻居继续搜索。
// 5. 整张网格扫描完后返回计数。
岛屿的最大面积
形象理解：每次从一块新陆地开始做“洪水填充”，搜索返回这座岛包含的格子数，再用它更新最大面积。
// 1. DFS 进入合法未访问陆地时先贡献面积 1。
// 2. 标记当前格，防止沿相邻格走回来形成无限递归。
// 3. 累加上下左右四个方向返回的面积。
// 4. 每次发现新岛调用 DFS，并更新全局最大值。
孤岛的最大面积
形象理解：从边界能走出去的陆地都不是封闭孤岛。先从四条边界出发淹掉所有相连陆地，剩余陆地才是被水完全包围的部分；原记录最终统计这些剩余陆地的总面积。
// 1. 遍历首尾行和首尾列。
// 2. 从边界陆地启动 DFS/BFS，将相连陆地标记为非孤岛。
// 3. 再扫描内部剩余陆地，通过 DFS 累加其总面积。
// 4. 已从边界访问的格子不再计入。
沉没孤岛（被围绕的区域）
形象理解：边界上的陆地 1 及其连通区域不会被包围，先给它们贴上临时安全标记 2；剩下的 1 全部沉成水域 0，最后再恢复安全区。
// 1. 从四条边界的陆地 1 出发搜索，临时改成安全标记 2。
// 2. 扫描整个网格，把仍为 1 的格子改成水域 0。
// 3. 这些未被边界搜索触达的 1 就是应被沉没的孤岛。
// 4. 再把所有安全标记 2 恢复为陆地 1。
太平洋大西洋水流问题
形象理解：正向从每个格子试着往低处流很重复。反过来分别从两片海岸向高处爬，能被两次逆向搜索都到达的格子，就能顺流到两片海。
// 1. 建立 pacificVisited 和 atlanticVisited 两张标记表。
// 2. 从上边界、左边界做逆向 DFS/BFS，邻格高度必须不低于当前格。
// 3. 从下边界、右边界做同样搜索。
// 4. 扫描所有格子，同时被两张表标记的坐标加入答案。
建造最大岛屿
形象理解：先给每座已有岛屿刷上独立颜色并记录面积。尝试把一个 0 改成 1 时，只需把上下左右不同颜色岛屿的面积相加，再加上新格子本身。
// 1. DFS 给每座岛分配 id >= 2，并在 area[id] 中记录面积。
// 2. 枚举每个水格 0，建立集合保存四邻域出现的不同岛 id。
// 3. candidate = 1 + 所有不同相邻岛面积之和。
// 4. 用 candidate 更新答案，集合负责防止同一岛重复相加。
// 5. 若没有水格，答案就是整张网格面积。
岛屿的周长
形象理解：每块陆地最初贡献四条边；每与另一块陆地共享一条边，总周长就少两条，因为两边都变成内部边。
// 1. 扫描每个陆地格，先令 perimeter += 4。
// 2. 只检查上方和左方，避免一对相邻陆地重复处理。
// 3. 上方是陆地时 perimeter -= 2。
// 4. 左方是陆地时 perimeter -= 2。
// 5. 返回最终周长。
单词接龙
形象理解：每个单词是节点，只差一个字符的单词之间有边。BFS 像从起点同时扩散的波纹，第一次碰到终点时走过的层数一定最少。
// 1. 将 wordList 放入哈希集合；endWord 不存在时直接返回 0。
// 2. beginWord 入队，并记录距离 1。
// 3. 弹出当前单词，逐位置尝试替换为 'a'..'z'。
// 4. 新单词在集合中时立即删除并入队，删除同时完成 visited 标记。
// 5. 第一次生成 endWord 时返回当前距离 + 1。
最小生成树与最短路
Prim 算法
形象理解：已经连通的节点形成一座岛，每轮选择从岛内伸向岛外最便宜的一座桥，把一个新节点纳入岛中。
// 1. minDist[v] 记录当前生成树连接到 v 的最小边权。
// 2. 每轮从未加入节点中选择 minDist 最小的 u。
// 3. 将 u 标记为已加入，并把 minDist[u] 加入总权重。
// 4. 用 u 的边更新所有未加入邻居的 minDist。
// 5. 重复 n 次；有节点始终不可达则图不连通。
Kruskal 算法
形象理解：把所有道路按造价从低到高排队，只要一条路连接的是两个不同村落联盟，就修建它；已经在同一联盟的两端再连会成环，必须跳过。
// 1. 将所有边按权重升序排序。
// 2. 初始化并查集，让每个节点自成连通块。
// 3. 扫描边，若 find(u) != find(v)，选择该边并 unite(u,v)。
// 4. 累加边权；选满 n-1 条边时生成树完成。
// 5. 同集合边直接跳过，避免形成环。
Dijkstra 朴素算法
形象理解：每轮从尚未确定的城市中选当前距离最近者。非负边保证以后绕路不可能让它更近，因此可以盖章确认，再用它帮助邻居缩短距离。
// 1. dist[source] = 0，其余为无穷大。
// 2. 每轮线性寻找未访问且 dist 最小的节点 u。
// 3. 标记 u 已确定。
// 4. 对 u 的每条边执行 dist[v] = min(dist[v], dist[u] + weight)。
// 5. 重复直到所有可达节点确定，复杂度 O(V^2)。
Dijkstra 堆优化
形象理解：最小堆替代“每轮在所有城市中找最近者”的线性搜索。堆里可能保留旧报价，弹出时若比最新 dist 更差就丢弃。
// 1. 将 (0, source) 放入最小堆。
// 2. 弹出 (distance, u)，若 distance != dist[u]，说明是过期记录，跳过。
// 3. 遍历 u 的邻边，若找到更短路径就更新 dist[v]。
// 4. 每次更新后把新的 (dist[v], v) 压入堆。
// 5. 非负权图上复杂度约 O((V+E)logV)。
拓扑排序
形象理解：入度为 0 的课程没有任何先修课，可以立即学习。学完它就删除其出边，后续课程的先修数量减少；不断重复直到没有可学课程。
// 1. 建立邻接表并统计每个节点入度。
// 2. 所有入度为 0 的节点入队。
// 3. 弹出节点加入拓扑序，并遍历它指向的邻居。
// 4. 邻居入度减一；降到 0 时入队。
// 5. 最终处理节点数等于 V 则无环，否则存在依赖环。
Bellman-Ford
形象理解：最短简单路径最多包含 V-1 条边。每一轮让已知最短距离沿所有边再传播一步，连续做 V-1 轮就能覆盖所有可能的简单路径。
// 1. dist[source] = 0，其余为无穷大。
// 2. 重复 V-1 轮扫描全部边 (u,v,w)。
// 3. u 可达且 dist[u] + w < dist[v] 时松弛 dist[v]。
// 4. 某轮没有任何更新时可提前结束。
// 5. 算法允许负权边，复杂度 O(VE)。
SPFA 队列优化
形象理解：Bellman-Ford 每轮检查所有边，SPFA 只让“距离刚刚变小的节点”去通知邻居；没有新消息的节点无需重复广播。
// 1. source 入队，并用 inQueue 防止同一节点重复排队。
// 2. 弹出 u 后令 inQueue[u] = false。
// 3. 松弛 u 的所有出边；dist[v] 变小时才需要继续传播。
// 4. 若 v 当前不在队列中，将它入队并标记。
// 5. 平均可能更快，但最坏复杂度仍为 O(VE)。
Bellman-Ford 判断负权回路
形象理解：V-1 轮后正常最短路已经稳定；若第 V 轮还能变短，说明路径可以绕某个负权环不断降价，不存在有限最短值。
// 1. 先完成至多 V-1 轮正常松弛。
// 2. 再额外扫描全部边一次。
// 3. 若仍存在 dist[u] + w < dist[v]，说明源点可达的负环存在。
// 4. SPFA 版本也可统计节点进入路径/队列的次数，达到 V 时判负环。
Bellman-Ford 单源有限最短路径
形象理解：题目限制最多经过 k 条边，就让距离只传播 k 轮。每轮必须读取上一轮的快照，避免同一轮连续使用多条边而突破边数限制。
// 1. dist[source] = 0，其余为无穷大。
// 2. 重复 k 轮，先复制 backup = dist。
// 3. 扫描边时使用 backup[u] + w 更新 dist[v]。
// 4. backup 确保第 i 轮只从“最多 i-1 条边”的结果转移。
// 5. k 轮后 dist[target] 即边数受限的最短距离。
Floyd 算法
形象理解：逐个开放中转站 k。开放第 k 个站后，任意 i 到 j 的路线可以保持原路，也可以改走 i -> k -> j，选更短者。
// 1. dist[i][i] = 0，有直接边时写入边权，其余为无穷大。
// 2. 最外层枚举中间节点 k，表示当前只允许使用 0..k 作中转。
// 3. 再枚举起点 i 和终点 j。
// 4. 两段都可达时更新 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
// 5. k 必须放在最外层；完成后得到任意两点最短路。