LeetCode 热题 100 · Java 题解

[!abstract] 这份笔记是什么
力扣站内刷题发烧友投票最多的 100 道题，按 17 个专题整理。每题给：思路脉络（为什么这么想）+ Mermaid 图 + 可跑的 Java 代码 + 复杂度 + 易错点。目标是建立"代码思维"——遇到新题能快速归类、套模板、处理边界，而不是背答案。

怎么用这份笔记

  • 先看每题的思路脉络，理解从暴力到最优的跃迁动因，这比代码本身重要。
  • Mermaid 图画的是数据结构怎么动，配合代码看。
  • 代码是 LeetCode 原题方法签名，复制即可提交；关键行有注释。
  • [!warning] 是真实踩坑，[!tip] 是通用套路，[!info] 是复杂度。

配图说明

复杂题配可视化分镜，放在 assets/ 目录：

  • 动图 .gif：算法关键状态逐帧切换，看"过程怎么动"。已全部上传阿里云 OSS，文档里用 ![](https://itbird.oss-cn-beijing.aliyuncs.com/img/2026/07/xxx.gif) 外链嵌入，全域分发无需带 assets 目录。

[!info] 制图流程
真实浏览器渲染 HTML → emulate 把 viewport 精确锁到内容尺寸（杜绝黑边）→ 逐帧截图 → ffmpeg 合成高分辨率 GIF。这套流程对过程感强的题（柱状图、链表翻转、DP 表填充、单调栈等）效果最好；简单题不配，免得冗余。GIF 通过 PicGo（HTTP server :36677）传到阿里云 OSS，原文件名保留。

题型分布

专题题数核心思维
哈希3用空间换时间，O(1) 查询建立"逆向映射"
双指针4有序/对撞/快慢，把两层循环压成一层
滑动窗口2左右指针维护一个满足约束的动态区间
子串3前缀和 + 哈希 / 单调队列优化窗口最值
普通数组5原地操作、区间合并、下标映射
矩阵4边界模拟、原地翻转、Z 字查找
链表14指针操作、哨兵节点、快慢指针
二叉树15递归三部曲：边界、单层逻辑、返回值传递
图论4DFS/BFS 染色、拓扑排序、Trie
回溯8选→递→撤销，用"做选择"的视角统一所有搜索题
二分查找6单调性 + 收缩边界，难点在边界处理
栈5后进先出匹配、单调栈求"下一个更大"
堆3Top-K、动态中位数，用堆维护"半个有序集"
贪心算法4局部最优推全局最优，需证明交换不会更差
动态规划10状态定义 + 转移方程 + 遍历顺序
多维动态规划5二维状态，行列/区间维度的扩展
技巧5位运算、摩尔投票、下标原地哈希

三条贯穿全程的代码思维

[!tip] 1. 暴力法是起点，不是终点
每道题先想清楚"暴力怎么做"，再问"哪一步在重复计算/可以跳过"。哈希、双指针、DP 的优化本质都是消除重复。

[!tip] 2. 数据结构是工具，先想"我需要什么操作"
需要"查询是否存在"→哈希；需要"两端伸缩"→双指针；需要"最近相关性"→栈；需要"动态最值"→堆/单调队列。先定操作需求，再选结构。

[!tip] 3. 边界是 Bug 的老家
空输入、单元素、全相同、最大最小值溢出、负数……每题写完先在脑子里跑这五个 case。

目录

  • [[#1. 哈希]] · 3 题
  • [[#2. 双指针]] · 4 题
  • [[#3. 滑动窗口]] · 2 题
  • [[#4. 子串]] · 3 题
  • [[#5. 普通数组]] · 5 题
  • [[#6. 矩阵]] · 4 题
  • [[#7. 链表]] · 14 题
  • [[#8. 二叉树]] · 15 题
  • [[#9. 图论]] · 4 题
  • [[#10. 回溯]] · 8 题
  • [[#11. 二分查找]] · 6 题
  • [[#12. 栈]] · 5 题
  • [[#13. 堆]] · 3 题
  • [[#14. 贪心算法]] · 4 题
  • [[#15. 动态规划]] · 10 题
  • [[#16. 多维动态规划]] · 5 题
  • [[#17. 技巧]] · 5 题

1. 哈希

哈希的本质是建立逆向映射：数组的值→下标、字符→出现次数、元素→是否存在。代价是 O(n) 空间，收益是把"查找"从 O(n) 降到 O(1)。

1. 两数之和

给数组 nums 和目标 target，返回和为 target 的两个元素的下标。恰好有一个解，同一元素不能重复用。

思路脉络：暴力是两层循环枚举所有数对，O(n²)。优化点在于——当我固定了 num，要找的就是 target - num 这个确定的值。确定值 + 要 O(1) 查询 → 哈希表。

关键细节：边查边存。如果先把所有元素存进 map，遇到 [3,3], target=6 这种重复值会覆盖下标，且没法保证不用同一元素。边查边存能保证查到的一定是当前元素之前出现过的，天然避免重复使用。

graph LR A["遍历 i, num=nums[i]"] --> B{"map 有 target-num?"} B -- 有 --> C["返回 [map.get(target-num), i]"] B -- 没有 --> D["map.put(num, i)"] D --> A

[!info] 流程图（图片版，用于不支持 Mermaid 的平台）
![[assets/mermaid/0001-two-sum.svg]]
PNG 版：assets/mermaid/0001-two-sum.png

[!example] 边查边存（动图）
[2,7,11,15] target=9：i=0 值2，need=7 不在 map，存 {2:0}；i=1 值7，need=2 在 map（下标0），命中返回 [0,1]。关键是先查再存——保证查到的是之前出现过的，天然避免用到自己（[3,3] target=6 也不会误匹配）。

0001-two-sum

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(); // 值 -> 下标
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)) {
                return new int[]{map.get(need), i}; // 先查再存，避免用到自己
            }
            map.put(nums[i], i);
        }
        return new int[0]; // 题目保证有解，走不到
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点
先存后查会让 [3,3] target=6 返回错误（自己匹配自己）。必须先查再存。

49. 字母异位词分组

把互为字母异位词的字符串归到一组。字母异位词：字母相同、排列不同。

思路脉络：异位词的本质是"字母构成相同"。要分组，就得给同组一个相同的 key。问题变成：怎么把一个字符串规范化成 key？

两种规范化方式：

  • 排序：把字符串字符排序，"eat"→"aet"。O(k log k)。
  • 计数：26 个字母的出现次数，拼成字符串当 key。O(k)。

排序写起来短，工程上 k 不大时排序往往更快（常数小）。计数在大 k 下渐进更优。

graph LR A["字符串 str"] --> B["规范化为 key"] B --> C{"map 含 key?"} C -- 有 --> D["加入该组列表"] C -- 没有 --> E["新建列表并加入"] D --> F["map.values() 即结果"] E --> F

排序法代码最直观：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] cs = s.toCharArray();
            Arrays.sort(cs);                  // 排序后作为 key
            String key = new String(cs);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

computeIfAbsent 是这里的关键 API：key 不存在就创建列表，存在就返回，省去手动 containsKey 判断。

[!info] 复杂度
时间 O(n·k log k)（n 是字符串数，k 是最长串长度），空间 O(n·k)。

[!tip] 套路
"按某种等价关系分组"通用解法：找规范化的 key + HashMap 分组。后续回文串、同构字符串都吃这一套。

128. 最长连续序列

给未排序数组，找最长连续整数序列的长度（如 [100,4,1,101,3,2] → 4，因为 1,2,3,4）。要求 O(n)。

思路脉络：排序是 O(n log n)，不达标。要 O(n) 必须用哈希。朴素哈希做法：把所有数放 set，对每个数 x 往上数 x+1, x+2... 看能走多远。但这会 O(n²)——比如全是连续数时，每个数都从头数一遍。

优化点：只有序列起点才值得扩展。如果 x-1 也在 set 里，那 x 不是起点，从 x 开始数一定会被从更小起点数过的结果覆盖。所以加一个判断 !set.contains(x-1)，只从起点往上数。

为什么是 O(n)？每个元素只在"作为起点向上扩展"时被访问，且扩展过程中访问的每个数都不会再作为起点（因为它们的前驱存在）。整体每个数最多被访问常数次。

graph LR A["全部数放入 Set"] --> B["遍历每个数 x"] B --> C{"x-1 在 Set 中?"} C -- 是 → 非起点，跳过 --> B C -- 否 → x 是起点 --> D["从 x 向上数 x+1, x+2..."] D --> E["更新最长长度"] E --> B 
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int best = 0;
        for (int x : set) {
            if (set.contains(x - 1)) continue; // 不是起点，跳过
            int cur = x, len = 1;
            while (set.contains(cur + 1)) { cur++; len++; }
            best = Math.max(best, len);
        }
        return best;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点
漏掉 x-1 判断会退化到 O(n²)。这个"只从起点扩展"的剪枝是本题 O(n) 的灵魂。

2. 双指针

双指针的核心是用两个指针的协同移动，把两层嵌套循环压成一层线性扫描。常见的三种形态：

  • 快慢指针：同向移动，一个探路一个收尾（移动零、删除重复项）。
  • 对撞指针：从两端向中间，配合单调性（盛水容器、三数之和）。
  • 归并指针：两个序列各一个指针，按序推进（合并有序链表/数组）。

判定用哪种的依据是：指针移动后，被跳过的解是否能安全排除。这是双指针正确性的根基。

283. 移动零

把数组中所有 0 移到末尾，保持非零元素相对顺序，原地操作。

思路脉络：本质是"把非零元素挑出来排前面，剩下的位置填 0"。用快慢指针：slow 标记下一个非零元素该放的位置，fast 扫描全数组。遇到非零就和 slow 交换，再 slow++。

为什么用交换而不是"覆盖后补 0"？交换一步到位，不用二次填充，且天然保持顺序。

graph LR A["slow=0 非零落脚点"] --> B["fast 遍历数组"] B --> C{"nums[fast] != 0?"} C -- 是 --> D["交换 slow 与 fast"] D --> E["slow++"] C -- 否 --> F["跳过"] E --> B F --> B 
class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                int t = nums[slow]; nums[slow] = nums[fast]; nums[fast] = t;
                slow++;
            }
        }
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 套路
快慢指针处理"原地分区/筛选"问题：slow 永远指向下一个符合条件元素的落脚点。同款的还有 [[#26. 删除有序数组中的重复项]] 思路、[[#75. 颜色分类]]。

11. 盛最多水的容器

数组 height 表示竖线高度，两根线与 x 轴围成容器，求最大盛水量。面积 = min(h[l], h[r]) × (r - l)。

思路脉络：暴力枚举所有数对 O(n²)。优化靠一个贪心剪枝：双指针从两端出发，宽 (r-l) 在缩小，要让面积变大只能指望高 min(h[l],h[r]) 变大。此时该移动哪边？

移动高的一边：高被 min 限制，移动后宽更小，且新边若更高也不会提升 min（被原矮边卡住），若更矮则 min 更小——面积必减。
移动矮的一边：矮边是瓶颈，换掉它才有可能让 min 变大。虽然不一定变好，但只有这条路有可能变好。

所以策略：哪边矮移哪边。

graph LR A["l=0, r=n-1"] --> B["算面积 min*宽"] B --> C["更新答案"] C --> D{"h[l] < h[r]?"} D -- 是 --> E["l++ 移矮边"] D -- 否 --> F["r-- 移矮边"] E --> B F --> B 
class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1, ans = 0;
        while (l < r) {
            int area = Math.min(height[l], height[r]) * (r - l);
            ans = Math.max(ans, area);
            if (height[l] < height[r]) l++; else r--;
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点
别写成"移动高的"。正确性证明要抓住"宽必减、高受 min 限制"两点，移动矮边是唯一可能变好的方向。

15. 三数之和

找所有和为 0 的不重复三元组。

思路脉络：三数和 = 固定一个 + 两数和。两数和在有序数组上可以用对撞双指针。所以先排序。固定 i，然后在 i+1..n-1 上用双指针找 nums[l]+nums[r] = -nums[i]。

难点不在算法，在去重。三个位置都可能重复：

  • i 去重：i > 0 && nums[i] == nums[i-1] 时跳过。
  • 找到一组解后，l 和 r 都要跳过相邻重复值。

[!tip] 剪枝
排序后若 nums[i] > 0，三个正数加起来不可能为 0，直接 break。

graph LR A["排序"] --> B["固定 i"] B --> C["l=i+1, r=n-1"] C --> D["sum = nums[i]+nums[l]+nums[r]"] D --> E{"sum ? 0"} E -- "<0" --> F["l++"] E -- ">0" --> G["r--"] E -- "=0" --> H["记录答案"] H --> I["l,r 各自跳过重复"] I --> J["l++, r--"] F --> D G --> D J --> D 
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;                       // 最小值已>0
            if (i > 0 && nums[i] == nums[i - 1]) continue; // i 去重
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum < 0) l++;
                else if (sum > 0) r--;
                else {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while (l < r && nums[l] == nums[l + 1]) l++;  // l 去重
                    while (l < r && nums[r] == nums[r - 1]) r--;  // r 去重
                    l++; r--;
                }
            }
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n²)（排序 O(n log n) + 双指针扫描），空间 O(log n) 排序栈。

[!warning] 易错点
去重判断用 nums[i] == nums[i-1]（与前一个比）而不是 nums[i] == nums[i+1]。后者会漏掉 -1,-1,2 这种合法解中第一个 -1。核心原则：跳过的是"后出现的重复"，保留"第一个出现的"。

42. 接雨水

柱状图接雨水，求能接住的水量。

思路脉络：每个位置 i 能接的水 = min(左边最高, 右边最高) - height[i]（若为正）。这是"按列计算"的本质。

[!example] 按列计算分镜（动图）
拆解四步：原始柱状 → 左侧最高 leftMax → 右侧最高 rightMax → 每列水量 min(左,右) − height，合计 6。

0042-trap-water

三种实现，一个比一个省空间：

方法一：DP 预处理两个数组。leftMax[i]、rightMax[i] 各扫一遍得到，再遍历求和。O(n) 时间 O(n) 空间，最好理解。

方法二：单调栈。按行算，遇到比栈顶矮的入栈，遇到更高的就弹出栈顶算一层。O(n) 时间 O(n) 空间，思路不同。

方法三：双指针 O(1) 空间。本题重点。leftMax 和 rightMax 不预先算，而是双指针移动时实时维护。关键洞察：

哪边矮就处理哪边。若 height[l] < height[r]，则 l 处的水量由 leftMax 决定——因为 rightMax 至少是 height[r]，比 height[l] 大，所以 min(leftMax, rightMax) 的瓶颈在 leftMax 一侧。

graph LR A["l=0,r=n-1<br/>leftMax=rightMax=0"] --> B{"h[l] < h[r]?"} B -- 是 --> C{"h[l] >= leftMax?"} C -- 是 --> D["更新 leftMax"] C -- 否 --> E["累加 leftMax-h[l]"] D --> F["l++"] E --> F B -- 否 --> G{"h[r] >= rightMax?"} G -- 是 --> H["更新 rightMax"] G -- 否 --> I["累加 rightMax-h[r]"] H --> J["r--"] I --> J F --> B J --> B 
class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1;
        int leftMax = 0, rightMax = 0, ans = 0;
        while (l < r) {
            if (height[l] < height[r]) {          // 左边矮，瓶颈在左
                if (height[l] >= leftMax) leftMax = height[l];
                else ans += leftMax - height[l];
                l++;
            } else {                              // 右边矮，瓶颈在右
                if (height[r] >= rightMax) rightMax = height[r];
                else ans += rightMax - height[r];
                r--;
            }
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点
双指针正确性的关键：处理某一边时，另一侧一定有一个 >= 当前侧 max 的柱子挡着。这正是 height[l] < height[r] 判断保证的——右边那个 height[r] 就充当了右侧最高的一部分保证。

[!tip] 关联
这题是"单调性 + 双指针"的巅峰，和 [[#11. 盛最多水的容器]] 一脉相承：都是"移动矮边"。但接雨水算的是"夹缝里能存多少"，盛水容器算的是"两根线能围多少"，方向相反。[[#84. 柱状图中最大的矩形]] 则用单调栈，思路又不同。

3. 滑动窗口

滑动窗口维护一个满足某约束的动态区间，靠左右指针交替前进避免重复计算。两类典型：

  • 可变窗口：r 扩张到违反约束，l 收缩到重新合法，过程中记录答案（最长无重复子串）。
  • 固定窗口：窗口大小恒定，整体平移，维护窗口内状态（异位词、窗口最大值）。

核心技巧是用一个"状态量"替代每次重算：维护 valid/match 计数，让"窗口是否合法"的判断变成 O(1)。

3. 无重复字符的最长子串

找不含重复字符的最长子串长度。

思路脉络：暴力是枚举所有子串 O(n³) 或固定起点向右延伸 O(n²)。观察：若子串 [l,r] 在 r 处出现重复字符 c，那么任何 l 不动的更长子串都含重复——l 必须跳过 c 上次出现的位置。

所以用哈希记下每个字符最近一次出现的下标，r 遇到重复时，l 直接跳到 map.get(c)+1。注意要用 max(l, ...)：因为重复字符可能已经在 l 左侧（窗口外），不能往回缩。

graph LR A["l=0, r 遍历"] --> B{"c 上次出现在窗口内?"} B -- 是 --> C["l 跳到 上次下标+1"] B -- 否 --> D["窗口合法"] C --> E["更新 c 位置, 更新答案"] D --> E E --> A 
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>(); // 字符 -> 最近下标
        int l = 0, ans = 0;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            if (map.containsKey(c)) {
                l = Math.max(l, map.get(c) + 1); // 只能前进，不能后退
            }
            map.put(c, r);
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(字符集大小)。

[!warning] 易错点
漏掉 Math.max 会导致 l 回退。例如 abba，处理第二个 b 时 l 跳到 2，处理第二个 a 时若直接用 map.get('a')+1 = 1，l 会从 2 退回 1，窗口反而变大且含重复。

438. 找到字符串中所有字母异位词

找 p 的所有异位词在 s 中的起始下标。

思路脉络：异位词 = 长度相同且字母计数相同。固定大小为 m = p.length() 的窗口在 s 上滑动，问哪些位置的窗口计数等于 p 的计数。

朴素做法每次滑完比较 26 个字母计数，O(26n)。优化：维护 valid——窗口与 need 计数相等的字母种类数。每次加入/移除一个字符，只影响该字符一处的相等关系，O(1) 更新 valid。当 valid == 26 时窗口与 p 完全匹配。

graph LR A["need = p 的计数"] --> B["窗口先填前 m 个字符"] B --> C["算初始 valid"] C --> D["r 从 m 滑到 n-1"] D --> E["加入 s[r], 移除 s[i-m]"] E --> F["O(1) 更新 valid"] F --> G{"valid == 26?"} G -- 是 --> H["记录起点"] G -- 否 --> D H --> D 
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int n = s.length(), m = p.length();
        if (n < m) return res;
        int[] need = new int[26], win = new int[26];
        for (int i = 0; i < m; i++) {
            need[p.charAt(i) - 'a']++;
            win[s.charAt(i) - 'a']++;
        }
        int valid = 0;
        for (int i = 0; i < 26; i++) if (need[i] == win[i]) valid++; // 含 need=0&win=0 的种
        if (valid == 26) res.add(0);
        for (int i = m; i < n; i++) {
            char in = s.charAt(i), out = s.charAt(i - m);
            // 加入 in
            if (need[in - 'a'] == win[in - 'a']) valid--; // 加入前相等, 加入后将不等
            win[in - 'a']++;
            if (need[in - 'a'] == win[in - 'a']) valid++;
            // 移除 out
            if (need[out - 'a'] == win[out - 'a']) valid--;
            win[out - 'a']--;
            if (need[out - 'a'] == win[out - 'a']) valid++;
            if (valid == 26) res.add(i - m + 1);
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)（26 个字母固定）。

[!tip] 套路
"定长滑动窗口 + 状态计数"是字符串匹配的万能模板。valid 计数法把"两个数组是否相等"压成单变量维护，是滑动窗口题提速的关键。后续 [[#76. 最小覆盖子串]] 是变长版本，思路同源。

4. 子串

这一类是「前缀和 / 滑动窗口」的进阶：要么用前缀和把区间问题转成两点关系，要么用单调队列给滑动窗口配一个能 O(1) 取最值的数据结构。

560. 和为 K 的子数组

统计数组中和为 k 的连续子数组个数。数组含负数。

思路脉络：第一反应可能是"排序 + 双指针"，但子数组必须连续、且含负数，排序破坏连续性、双指针依赖单调性（负数让和不再单调）——这条路堵死。

正确切入点是前缀和。设 pre[i] 是前 i 项和，则子数组 [j+1, i] 的和 = pre[i] - pre[j]。要让它等于 k，就是找 pre[j] = pre[i] - k。

边算前缀和边用哈希记录"之前出现过哪些前缀和、各几次"，当前 pre 减 k 能在哈希里命中多少个，就有多少个以 i 结尾的合法子数组。一次遍历搞定。

graph LR A["维护前缀和 pre"] --> B{"map 含 pre-k?"} B -- 是 --> C["ans += 出现次数"] B -- 否 --> D["map[pre]++"] C --> D D --> A 
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);                  // 前缀和 0 出现 1 次, 处理从下标 0 起的子数组
        int pre = 0, ans = 0;
        for (int n : nums) {
            pre += n;
            if (map.containsKey(pre - k)) ans += map.get(pre - k);
            map.merge(pre, 1, Integer::sum);
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点
必须初始化 map.put(0, 1)。否则形如 nums=[k]、整个数组本身就是答案时，pre-k=0 命中不到。另外，不能先存再查：要先查当前 pre，再把 pre 入 map，否则 k=0 时会把自己算进去。

[!tip] 辨析
「和为 K 的子数组」有三种变形，解法完全不同：

  • 数组含负数（本题）→ 前缀和 + 哈希，O(n)。
  • 数组全正数 → 滑动窗口，O(n)。
  • 求最大长度 → 同样前缀和+哈希，存最早出现位置。

239. 滑动窗口最大值

大小为 k 的窗口从左滑到右，返回每个位置窗口内的最大值。

思路脉络：朴素是每个窗口扫一遍找最大，O(nk)。优化点：窗口每次只进出各一个元素，最大值的变化是"局部"的——一个元素一旦被右侧更大的元素超过，它在剩余窗口里就永远当不了最大，可以丢弃。

这就是单调递减队列：队列存下标，从队尾入队前，把所有比当前元素小的队尾弹出（它们没用了）。队首永远是当前窗口最大值。再处理一个过期：队首下标若已滑出窗口就弹出。

graph LR A["遍历 i"] --> B["弹出队尾所有 ≤ nums[i] 的"] B --> C["i 入队尾"] C --> D{"队首下标 < i-k+1?"} D -- 是 --> E["队首过期, 弹出"] D -- 否 --> F{"i ≥ k-1?"} E --> F F -- 是 --> G["记录 nums[队首]"] F -- 否 --> A G --> A 
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> dq = new ArrayDeque<>(); // 存下标, 单调递减
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (dq.peekFirst() <= i - k) dq.pollFirst(); // 队首过期
            if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)（每个元素入队出队各一次），空间 O(k)。

[!tip] 套路
单调队列处理"滑动窗口最值"。存下标而非值有两个好处：一能判断过期，二能通过下标取到原值。这是 [[#84. 柱状图中最大的矩形]] 单调栈的同族技巧，区别只在一端进出一端进出。

76. 最小覆盖子串

在 s 中找覆盖 t 所有字符的最短子串。

思路脉络：这是 [[#438. 找到字符串中所有字母异位词]] 的变长升级版。窗口不再固定大小，而是：r 扩张到"刚好覆盖 t"，l 收缩到"刚好不覆盖"，这个临界位置就是一个候选最短窗口。

用 valid 记录"窗口里满足需求计数的字符种类数"，valid == need.size() 表示已覆盖。覆盖时不断缩 l 并更新最小答案；一旦缩到不覆盖，就退出去继续扩 r。

graph LR A["r 扩张, 加入字符"] --> B{"valid == 需求种类数?"} B -- 否 --> A B -- 是 --> C["缩 l"] C --> D["更新最小窗口"] D --> E["移除 s[l], l++"] E --> F{"仍覆盖?"} F -- 是 --> C F -- 否 --> A 
class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
        Map<Character, Integer> win = new HashMap<>();
        int l = 0, valid = 0, needCnt = need.size();
        int start = 0, minLen = Integer.MAX_VALUE;
        for (int r = 0; r < s.length(); r++) {
            char c = s.charAt(r);
            if (need.containsKey(c)) {
                win.merge(c, 1, Integer::sum);
                if (win.get(c).equals(need.get(c))) valid++;
            }
            while (valid == needCnt) {          // 覆盖了, 尝试缩
                if (r - l + 1 < minLen) { minLen = r - l + 1; start = l; }
                char d = s.charAt(l++);
                if (need.containsKey(d)) {
                    if (win.get(d).equals(need.get(d))) valid--; // 移除后该种将不满足
                    win.merge(d, -1, Integer::sum);
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

[!info] 复杂度
时间 O(n)，空间 O(字符集)。

[!warning] 易错点
valid 只在"刚好达到需求"时 ++，在"刚好跌破需求"时 --，避免多算。判断"跌破"必须在减少计数之前比较，顺序反了会漏更新。needCnt 用 need.size()（去重后的种类数），不是 t.length()，因为同字符重复只算一种。

5. 普通数组

数组的题多靠原地操作和下标映射。核心是利用"下标本身也是一种信息"——把元素归位、把下标当哈希。

53. 最大子数组和

找和最大的连续子数组，返回和。

思路脉络：两种等价视角。

DP 视角：dp[i] 表示以 i 结尾的最大子数组和。要么把 nums[i] 续在前一段后面（dp[i-1]+nums[i]），要么从 nums[i] 重新开始（nums[i]），取大者。状态只依赖上一个，压缩成一个变量 pre。

前缀和视角：子数组和 = 当前前缀和 − 之前最小前缀和。维护一个最小前缀和即可。

两种都 O(n)。DP 写法更常用。

graph LR A["遍历 num"] --> B["pre = max(num, pre+num)"] B --> C["ans = max(ans, pre)"] C --> A 
class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, ans = Integer.MIN_VALUE;
        for (int n : nums) {
            pre = Math.max(n, pre + n); // 续上 或 从头
            ans = Math.max(ans, pre);
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点
ans 初值用 Integer.MIN_VALUE 而非 0，因为全负数组答案也是负数。pre 初值 0 配合 max(n, pre+n) 自动处理首元素。

56. 合并区间

合并所有重叠的区间。

思路脉络：区间若能合并，起点一定相邻。按起点排序后，遍历时只需关心"当前区间起点是否落在上一个已合并区间的终点内"——是则合并（终点取 max），否则新开一段。

graph LR A["按起点排序"] --> B["遍历每个区间"] B --> C{"起点 ≤ 末区间终点?"} C -- 是 --> D["合并: 终点取 max"] C -- 否 --> E["新开一段"] D --> B E --> B 
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        for (int[] iv : intervals) {
            if (!res.isEmpty() && iv[0] <= res.get(res.size() - 1)[1]) {
                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], iv[1]);
            } else {
                res.add(iv);
            }
        }
        return res.toArray(new int[0][]);
    }
}

[!info] 复杂度
时间 O(n log n)（排序），空间 O(排序栈)。

[!warning] 易错点
合并时终点必须取 max，不能直接覆盖。反例：[1,5] 与 [2,3]，覆盖成 [1,3] 就错了。

189. 轮转数组

数组右轮转 k 步，原地。

思路脉络：三种做法。

额外数组：res[(i+k)%n] = nums[i]，再拷回。O(n) 空间，最稳。
环状替换：从下标 0 出发，沿 (i+k)%n 链把元素逐个送到目标位置，回到起点换下一条链。需用 gcd(n,k) 算链数。O(1) 空间但容易写错。
三次反转（推荐）：整体反转 → 反转前 k 个 → 反转后 n-k 个。数学上恰好等价于右轮转 k，且代码极简。

[!example] 三次反转推演（动图）
[1,2,3,4,5,6,7] k=3：整体反转让后 k 个挪到前面（倒序），再分别反转前后两段恢复内部顺序，得到 [5,6,7,1,2,3,4]。

0189-rotate

graph LR A["k %= n"] --> B["反转 0..n-1"] B --> C["反转 0..k-1"] C --> D["反转 k..n-1"] 
class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;                          // k 可能大于 n
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    void reverse(int[] a, int l, int r) {
        while (l < r) { int t = a[l]; a[l] = a[r]; a[r] = t; l++; r--; }
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点
忘记 k %= n 会导致越界或重复转。空数组、k=0 要先处理（上面的写法对 k=0 也成立，反转 0 个元素是空操作）。

238. 除自身以外数组的乘积

返回每个位置上"除自身外其他元素乘积"，不能用除法，O(n)。

思路脉络：不用除法就只能拆成左右两半乘积。res[i] = 左侧所有元素乘积 × 右侧所有元素乘积。两趟扫描：先从左累乘把左侧乘积填进 res，再从右用一个变量累乘右侧乘积乘进去。

graph LR A["第一趟: 左到右"] --> B["res[i] = res[i-1]*nums[i-1]"] B --> C["res 存好左侧乘积"] C --> D["第二趟: 右到左"] D --> E["res[i] *= right; right *= nums[i]"] E --> F["res 存最终结果"] 
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 1; i < n; i++) res[i] = res[i - 1] * nums[i - 1]; // 左乘积
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] *= right;     // 乘上右侧乘积
            right *= nums[i];    // 更新右侧乘积
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)（结果数组不计额外空间）。

[!tip] 套路
"不能用除法求两侧乘积"标准两趟扫描。这个"前缀积 + 后缀积"的思想和 [[#除自身以外数组的乘积|前缀和]] 是一族，区别在一用积一用和。

41. 缺失的第一个正数

找数组中未出现的最小正整数。要求 O(n) 时间 O(1) 空间。

思路脉络：O(n) 时间暗示哈希，O(1) 空间又不能用额外哈希表——那就把数组本身当哈希表。

观察：答案一定在 [1, n+1]（n 是长度）。若数组含 1..n 全部，答案是 n+1；否则缺的那个在 [1,n] 内。所以只关心 [1,n] 范围内的数，把它们归位到"下标 = 值-1"的位置。归位后再扫一遍，第一个 nums[i] != i+1 的 i+1 即答案。

归位用 while 循环：交换后新来的元素可能也该归位，要持续交换直到当前位置的值不在范围或已在正确位置。

[!example] 原地哈希归位（动图）
[3,4,-1,1]：把每个 [1,n] 内的值 v 交换到下标 v-1 处，[1,n] 外的（如 -1）忽略。归位后扫一遍，第一个 nums[i]≠i+1 的 i+1 即答案（本例 index1=-1≠2，答案 2）。while 持续交换是关键。

0041-first-missing

graph LR A["遍历每个位置"] --> B{"nums[i] 在 [1,n] 且未归位?"} B -- 是 --> C["交换到 nums[i]-1 位置"] C --> B B -- 否 --> D["i++"] D --> E["扫一遍找 nums[i]≠i+1"] E --> F["返回 i+1, 否则 n+1"] 
class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (1 <= nums[i] && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                int t = nums[nums[i] - 1];      // 先存目标位原值
                nums[nums[i] - 1] = nums[i];    // 归位
                nums[i] = t;                    // 换回来的继续判断
            }
        }
        for (int i = 0; i < n; i++) if (nums[i] != i + 1) return i + 1;
        return n + 1;
    }
}

[!info] 复杂度
时间 O(n)（每个元素最多被交换到正确位置一次），空间 O(1)。

[!warning] 易错点
交换顺序坑死人不偿命：必须先存 nums[nums[i]-1] 到临时变量，再赋值 nums[nums[i]-1] = nums[i]，最后 nums[i] = t。若先写 nums[i] = nums[nums[i]-1]，则 nums[i] 已变，后续 nums[i]-1 这个索引就错了。while 条件里 nums[i] != nums[nums[i]-1] 防止重复值死循环。

[!tip] 关联
这是"原地哈希"的经典。同族的还有 [[#287. 寻找重复数]]（下标原地标记）、[[#442. 数组中重复的数据]]。套路都是：用下标承载信息，用值定位下标。

6. 矩阵

矩阵题集中在边界模拟和坐标变换。关键是要找到能简化判断的"锚点"——比如搜索二维矩阵的右上角、旋转图像的转置分解。

73. 矩阵置零

若 matrix[i][j]==0，把它所在的行和列全置零。原地。

思路脉络：朴素是开两个集合记录哪些行哪些列要置零，O(m+n) 空间。要 O(1) 空间，就把这个记录任务交给第一行和第一列本身：用 matrix[i][0] 标记第 i 行是否置零，matrix[0][j] 标记第 j 列是否置零。

但第一行/第一列自己也可能要置零，得用两个额外布尔变量单独记它们，否则会被自己的标记污染。处理顺序：先标记 → 再据标记清内部 → 最后清首行首列。

graph LR A["两个布尔标记首行首列是否含0"] --> B["遍历内部, 用首行首列记0位"] B --> C["据首行首列标记清内部"] C --> D["最后据布尔标记清首行首列"] 
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean firstRow = false, firstCol = false;
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) firstRow = true;
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) firstCol = true;
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; }
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
        if (firstRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
        if (firstCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(1)。

[!warning] 易错点
顺序不能乱：必须最后处理首行首列。若先清了首行，再用它当标记去清内部就全错了。

54. 螺旋矩阵

按顺时针螺旋顺序返回矩阵所有元素。

思路脉络：维护 top/bottom/left/right 四个边界，按"上→右→下→左"四条边遍历，每遍历完一条就收缩对应边界。难点在最后一圈可能只剩一行或一列，要避免重复遍历——所以后两条边遍历前先判断边界是否还交叉。

[!example] 四边界螺旋收缩（动图）
3×3 矩阵顺时针走边：→顶行后 top++、↓右列后 right--、←底行后 bottom--、↑左列后 left++，边界交叉即停。后两条边前判 top≤bottom/left≤right 防单行单列重复。

0054-spiral-matrix

graph LR A["top/bottom/left/right 四边界"] --> B["→遍历顶行, top++"] B --> C["↓遍历右列, right--"] C --> D{"top≤bottom? →遍历底行, bottom--"} D --> E{"left≤right? ↑遍历左列, left++"} E --> F{"边界未交叉?"} F -- 是 --> B F -- 否 --> G["结束"] 
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) res.add(matrix[top][j]); top++;
            for (int i = top; i <= bottom; i++) res.add(matrix[i][right]); right--;
            if (top <= bottom) { for (int j = right; j >= left; j--) res.add(matrix[bottom][j]); bottom--; }
            if (left <= right) { for (int i = bottom; i >= top; i--) res.add(matrix[i][left]); left++; }
        }
        return res;
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(1)（不计结果）。

[!warning] 易错点
后两条边（底行、左列）的遍历前必须检查 top<=bottom、left<=right，否则在只剩一行/一列时会重复添加。

48. 旋转图像

n×n 矩阵顺时针旋转 90°，原地。

思路脉络：直接找坐标映射——顺时针 90° 把 (i,j) 移到 (j, n-1-i)。原地四点轮换能做，但要分组、易错。

更优雅的分解：顺时针 90° = 主对角线转置 + 左右翻转。

  • 转置：(i,j)→(j,i)
  • 左右翻转：(j,i)→(j, n-1-i)
  • 合起来 (i,j)→(j, n-1-i)，正是顺时针 90°。

两步都用现成的原地操作，代码极简。

[!example] 转置 + 行翻转（动图）
3×3 矩阵：先沿主对角线转置（行列互换），再每行左右翻转，合起来正是顺时针 90°。两步都是原地 O(n²) O(1)。

0048-rotate-image

graph LR A["原矩阵"] --> B["沿主对角线转置"] B --> C["每行左右翻转"] C --> D["顺时针90°结果"] 
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++)            // 转置
            for (int j = i + 1; j < n; j++) {
                int t = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = t;
            }
        for (int[] row : matrix) {            // 每行翻转
            int l = 0, r = n - 1;
            while (l < r) { int t = row[l]; row[l] = row[r]; row[r] = t; l++; r--; }
        }
    }
}

[!info] 复杂度
时间 O(n²)，空间 O(1)。

[!tip] 记忆
四种旋转的分解：

  • 顺时针 90°：转置 + 行翻转
  • 逆时针 90°：转置 + 列翻转
  • 180°：行翻转 + 列翻转
    转置只遍历主对角线上方（j>i），否则会交换两次回到原样。

240. 搜索二维矩阵 II

m×n 矩阵，每行从左到右递增、每列从上到下递增。判断 target 是否存在。

思路脉络：暴力 O(mn)。逐行二分 O(m log n)。但有个更妙的 O(m+n)——从右上角出发。

右上角的妙处：往左是变小、往下是变大，两个方向单调性相反，每次比较能确定排除一行或一列。左上角不行（往右往下都变大，无法决策），右下角同理（都变小）。所以锚点必须选右上或左下。

[!example] 右上角 Z 字查找（动图）
target=5：从右上角 15 出发，当前值大于 target 就左移（排除当前列下方），小于 target 就下移（排除当前行左侧），每步排除一行或一列，O(m+n) 命中。锚点选右上是因为两方向单调性相反、可决策。

0240-search-matrix2

graph LR A["从右上角出发"] --> B{"当前值 ? target"} B -- "相等" --> C["返回 true"] B -- "更大" --> D["左移 j--"] B -- "更小" --> E["下移 i++"] D --> F{"越界?"} E --> F F -- 否 --> B F -- 是 --> G["返回 false"] 
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = n - 1;                       // 右上角
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) return true;
            else if (matrix[i][j] > target) j--;    // 太大, 这一列下面更大, 排除整列
            else i++;                               // 太小, 这一行左边更小, 排除整行
        }
        return false;
    }
}

[!info] 复杂度
时间 O(m+n)（每次排除一行或一列），空间 O(1)。

[!warning] 易错点
起点选错就废。能作为决策锚点的前提是"两个方向单调性相反"，只有右上、左下两个角满足。选左上会陷入"两边都可能"的困境。

7. 链表

链表题的通用心法有三条：

  1. 哨兵节点（dummy）：在头前加一个假节点，统一处理"头被改"的情况，省掉 if (head == ...) 特判。链表题 80% 都该用它。
  2. 快慢指针：找中点、找环、找倒数第 N 个，全靠两个指针步长差。
  3. 画图：链表题最忌凭脑内想象改指针，一定画图看清 next 指向再动手。

160. 相交链表

两个单链表在某节点开始共享后续节点，找这个交点。

思路脉络：两链表长度不同，对齐起点是关键。让两个指针走对方的路径：pA 走完 A 再走 B 的头，pB 走完 B 再走 A 的头。两者走过的总长度都是 a+b，长度差被抹平，若有交点必在某一刻相遇于交点；若无交点，两者同时走到 null 退出。

graph LR A["pA 走 A, pB 走 B"] --> B["pA 到尾 → 转向 B 头"] B --> C["pB 到尾 → 转向 A 头"] C --> D["同速继续"] D --> E{"pA == pB?"} E -- 是 --> F["返回交点"] E -- 否 --> D 
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next; // 到尾就跳到另一条的头
            pB = pB == null ? headA : pB.next;
        }
        return pA; // 相交则交点, 不相交则同时到 null
    }
}

[!info] 复杂度
时间 O(m+n)，空间 O(1)。

[!tip] 关键
用 p == null 而非 p.next == null 判断"到尾"——这样不相交时两指针都会各自走完 a+b 到达 null 而退出，不会死循环。

206. 反转链表

反转单链表。

思路脉络：迭代法用 prev/cur 双指针，逐个把 cur.next 指向 prev，再整体右移。注意先存 next 再改指针，否则丢链。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next; // 先存
            cur.next = prev;           // 反转指向
            prev = cur;                // 右移
            cur = next;
        }
        return prev; // 新头是原尾
    }
}

递归版思路：reverse(head) 返回反转后的新头，并让 head.next.next = head 把自己接到尾部。面试常考递归写法，体会"反过来的视角"。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head; // 后继指回自己
        head.next = null;      // 断开原方向
        return newHead;
    }
}

[!info] 复杂度
时间 O(n)，空间迭代 O(1) / 递归 O(n)。

[!warning] 易错点
head.next.next = head 这行是递归版的灵魂，理解为"让我的后继指向我"。漏了 head.next = null 会成环。

234. 回文链表

判断链表是否回文。进阶 O(n) 时间 O(1) 空间。

思路脉络：最稳的 O(n) 空间做法是复制到数组双指针比对。要 O(1) 空间：用快慢指针找中点 → 反转后半段 → 前后两半逐个比较 → （可选）反转恢复。

快慢找中点：fast 走两步、slow 走一步，fast 到尾时 slow 在中点。奇数长度 slow 落在正中，后半段从 slow.next 开始反转更对称。

graph LR A["快慢找中点 slow"] --> B["反转 slow 之后半段"] B --> C["前半 vs 反转后半 逐个比"] C --> D{"全相等?"} D -- 是 --> E["回文"] D -- 否 --> F["非回文"] 
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
        }
        ListNode second = reverse(slow); // 反转后半
        ListNode p1 = head, p2 = second;
        while (p2 != null) {
            if (p1.val != p2.val) return false;
            p1 = p1.next; p2 = p2.next;
        }
        return true;
    }
    ListNode reverse(ListNode h) {
        ListNode prev = null, cur = h;
        while (cur != null) { ListNode nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
        return prev;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

  • 比较循环用 p2 != null 而非 p1 != null：后半段反转后更短（奇数长度时中点不计），用短的作终止条件。否则 p1 会多走一个中点节点。

141. 环形链表

判断链表是否有环。

思路脉络：快慢指针，fast 每次两步、slow 每次一步。若有环，fast 终会追上 slow（在环里套圈）；若无环，fast 先到 null。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

  • 循环条件 fast != null && fast.next != null，缺 fast.next 会在 fast 是尾节点时 fast.next.next 空指针。slow/fast 同起点，先走再比，避免一开始就相等。

142. 环形链表 II

找到环的入口节点。无环返回 null。

思路脉络：[[#141. 环形链表]] 找"有没有环"，这题找"入口在哪"。复用快慢相遇，再加一段数学。

设：a = 头到入口距离，b = 入口到相遇点距离，c = 相遇点到入口距离（环长 = b+c）。

  • 慢指针走 a+b，快指针走 a + b + n(b+c)（多绕 n 圈，n≥1）。
  • 快是慢两倍：2(a+b) = a + b + n(b+c) → a = (n-1)(b+c) + c。

意思是：从头走 a 步 = 从相遇点在环里走 c 步，两者都恰好到入口。所以让一个指针回 head，两者同速前进，再次相遇即入口。

[!example] 快慢相遇 → 回头同速找入口（动图）
3→2→0→-4（-4 指回 2）：快慢在下标2(值0)相遇 → 一指针回 head → 同速前进在下标1(值2)再次相遇，即环入口。

0142-cycle-list2

graph LR A["快慢相遇于 meet"] --> B["一个指针回 head"] B --> C["两指针同速前进"] C --> D["再次相遇 = 环入口"] 
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) {                // 相遇
                ListNode p = head;
                while (p != slow) { p = p.next; slow = slow.next; }
                return p;                      // 入口
            }
        }
        return null;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 记忆

  • 相遇后"一个回起点同速再走"是关键动作。背下 a = (n-1)(b+c) + c 这步推导，面试常被追问。

21. 合并两个有序链表

合并两个升序链表。

思路脉络：经典归并的链表版。用 dummy 哨兵，逐个比较小的接上，剩余的直接挂上。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; }
            else { cur.next = l2; l2 = l2.next; }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2; // 剩余直接接上
        return dummy.next;
    }
}

[!info] 复杂度
时间 O(m+n)，空间 O(1)。

[!tip] 套路

  • 哨兵 dummy 是链表归并/构造类题的标配，省去头节点的空判。这题是 [[#23. 合并 K 个升序链表]] 的子问题。

2. 两数相加

两个链表逆序存两个非负整数（头是低位），返回和的链表。

思路脉络：模拟手工加法，从低位（头）开始逐位相加，维护进位 carry。循环条件要把 carry != 0 也算进去，否则最高位的进位会漏。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), cur = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) { sum += l1.val; l1 = l1.next; }
            if (l2 != null) { sum += l2.val; l2 = l2.next; }
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
        }
        return dummy.next;
    }
}

[!info] 复杂度
时间 O(max(m,n))，空间 O(max(m,n))。

[!warning] 易错点

  • 循环条件漏 carry != 0：形如 5+5=10，最后会多出一个进位节点 0→1，漏了就少一位。

19. 删除链表的倒数第 N 个结点

删除倒数第 N 个节点，要求一次遍历。

思路脉络：找倒数第 N 个，朴素是先数长度再走 len-n。一次遍历做法：快慢指针，fast 先走 n 步，再和 slow 同速，fast 到尾时 slow 恰在倒数第 N+1 个（待删的前驱）。用 dummy 是为了处理"删头"这种边界——否则删头时找不到前驱。

graph LR A["fast 先走 n 步"] --> B["fast/slow 同速前进"] B --> C{"fast.next == null?"} C -- 是 --> D["slow 在待删前驱"] D --> E["slow.next = slow.next.next"] C -- 否 --> B 
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        for (int i = 0; i < n; i++) fast = fast.next;     // fast 先走 n 步
        while (fast.next != null) { fast = fast.next; slow = slow.next; }
        slow.next = slow.next.next;                       // 删除
        return dummy.next;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

  • 不加 dummy，删头（n == 长度）时 slow 是 null，无法 slow.next。dummy 把所有删除统一成"删某个中间节点"。

24. 两两交换链表中的节点

两两交换相邻节点，如 1→2→3→4 变 2→1→4→3。

思路脉络：迭代法，用 cur 指向待交换对的前驱。每轮处理 a=cur.next、b=a.next，三步改指针：a.next=b.next、b.next=a、cur.next=b，然后 cur=a 推进。

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head), cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            ListNode a = cur.next, b = a.next;
            a.next = b.next;
            b.next = a;
            cur.next = b;
            cur = a; // a 现在是这对的尾, 作为下一对的前驱
        }
        return dummy.next;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 套路

  • 链表"改指针"题的万能姿势：用 cur 作前驱，每轮只看 cur.next 和 cur.next.next 两个节点，改完 cur 推进。和 [[#25. K 个一组翻转链表]] 同构。

25. K 个一组翻转链表

每 k 个节点一组翻转，不足 k 个保持原样。

思路脉络：[[#206. 反转链表]] + [[#24. 两两交换链表中的节点]] 的组合。外层按 k 分组，每组用区间反转，再把翻转后的头尾接回主链。

关键工具：一个 reverse(head, tail) 反转 [head, tail] 闭区间并返回 [新头, 新尾]。实现技巧是让 prev 从 tail.next 开始——这样反转后 head（变新尾）的 next 自动指向 tail.next，省去额外处理。

[!example] 分组反转接回（动图）
1→2→3→4→5 k=2：每组数 k 个定 tail，区间反转后头尾接回主链，不足 k 保持原样。最终 2→1→4→3→5。reverse 里 prev 从 tail.next 起是省处理的关键。

0025-reverse-kgroup

graph LR A["pre=dummy"] --> B["数 k 个找 tail"] B --> C{"不足 k?"} C -- 是 --> D["返回 dummy.next"] C -- 否 --> E["记 nxt=tail.next"] E --> F["反转 head..tail"] F --> G["pre.next=新头, 新尾.next=nxt"] G --> H["pre=新尾, head=nxt"] H --> B 
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head), pre = dummy;
        while (head != null) {
            ListNode tail = pre;
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                if (tail == null) return dummy.next; // 不足 k, 不翻
            }
            ListNode nxt = tail.next;
            ListNode[] rev = reverse(head, tail); // rev[0]=新头, rev[1]=新尾
            head = rev[0]; tail = rev[1];
            pre.next = head;   // 接回头
            tail.next = nxt;   // 接回尾
            pre = tail;
            head = nxt;
        }
        return dummy.next;
    }
    ListNode[] reverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next, cur = head; // prev 从 tail.next 起
        while (prev != tail) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return new ListNode[]{tail, head}; // 翻转后 tail 是头, head 是尾
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

  • reverse 里 prev 从 tail.next 开始而非 null，是为了让翻转后 head.next 直接指向原 tail.next，省一步。这是这题最妙的细节，想通了就不易错。
  • tail == null 时直接返回，不能把剩余不足 k 的也翻转——题意要求保持原样。

138. 随机链表的复制

链表节点有 next 和 random 指针，深拷贝整个链表。

思路脉络：难点在 random 指向任意位置，复制时要建立"旧节点→新节点"的映射。哈希法两遍扫描：第一遍建所有新节点存 map，第二遍据旧节点的 next/random 查 map 连新节点。

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Map<Node, Node> map = new HashMap<>();
        for (Node p = head; p != null; p = p.next) map.put(p, new Node(p.val));
        for (Node p = head; p != null; p = p.next) {
            map.get(p).next = map.get(p.next);       // null 也安全: map.get(null)=null
            map.get(p).random = map.get(p.random);
        }
        return map.get(head);
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!tip] 进阶

  • O(1) 空间做法：原地把每个新节点插在旧节点后（A→A'→B→B'），再设 random，最后拆链。但哈希法更易写易读，面试首选。

148. 排序链表

链表排序，O(n log n) 时间 O(1) 空间（递归栈不算）。

思路脉络：链表不支持随机访问，快排不友好。归并排序完美适配：找中点（快慢指针）→ 断开 → 递归排两半 → 合并（[[#21. 合并两个有序链表]]）。

找中点细节：fast 从 head.next 起步（而非 head），让 slow 落在前半末尾，方便断开。奇数长度时前半多一个，不影响归并。

graph LR A["快慢找中点 mid"] --> B["断开: mid.next=null"] B --> C["递归排前半"] B --> D["递归排后半"] C --> E["merge 两半"] D --> E 
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode mid = mid(head);
        ListNode right = mid.next;
        mid.next = null;                          // 断开
        return merge(sortList(head), sortList(right));
    }
    ListNode mid(ListNode head) {
        ListNode slow = head, fast = head.next; // fast 先走一步
        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
        return slow;
    }
    ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0), cur = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { cur.next = a; a = a.next; }
            else { cur.next = b; b = b.next; }
            cur = cur.next;
        }
        cur.next = a != null ? a : b;
        return dummy.next;
    }
}

[!info] 复杂度
时间 O(n log n)，空间 O(log n)（递归栈，自底向上迭代可做到 O(1)）。

[!warning] 易错点

  • 不 mid.next = null 断开会死循环——递归时前半仍连着后半。
  • fast 从 head.next 起：若从 head 起，两个节点时会停在第一个，前半空、死循环。

23. 合并 K 个升序链表

合并 k 个升序链表。

思路脉络：朴素每次从 k 个头里找最小，O(kn·k)。优化用小顶堆：把 k 个头入堆，每次弹出最小接上，并把它的 next 入堆。O(n log k)。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode h : lists) if (h != null) pq.offer(h);
        ListNode dummy = new ListNode(0), cur = dummy;
        while (!pq.isEmpty()) {
            ListNode node = pq.poll();
            cur.next = node;
            cur = cur.next;
            if (node.next != null) pq.offer(node.next);
        }
        return dummy.next;
    }
}

[!info] 复杂度
时间 O(n log k)（n 是总节点数，k 是链表数），空间 O(k)。

[!tip] 另解

  • 分治两两合并，也是 O(n log k)，不依赖堆。把 [[#21. 合并两个有序链表]] 当子程序，两两配对合并 k/2 组，再 k/4…直到剩一个。

146. LRU 缓存

实现 get/put 均 O(1) 的 LRU 缓存。容量满时淘汰最久未使用。

思路脉络：O(1) 查找 → 哈希；O(1) 调整顺序 → 双向链表。两者结合：哈希存 key→节点，双向链表维护访问顺序，最近访问的在头，最久未访问的在尾。

  • get：哈希查到节点 → 移到头部。
  • put：存在则更新值并移头；不存在则新建加头，超容则删尾并从哈希删。

双向链表用 head/tail 两个 dummy 节点包夹，省去空判。节点要存 key，因为淘汰尾节点时需要用 key 从哈希里删。

[!example] 哈希+双向链表访问序（动图）
容量 2：put(1,1)→put(2,2)→get(1) 命中移头→put(3,3) 淘汰尾2→put(4,4) 淘汰尾1。头=最近(MRU)、尾=最久(LRU)，超容删尾。节点必须存 key 才能从哈希删。

0146-lru-cache

graph LR A["dummy头 ↔ ... ↔ 尾前 ↔ dummy尾"] --> B["get: 查 map, 命中则 moveToHead"] B --> C["put: 存在则改值 moveToHead"] C --> D["put: 不存在则新建加头"] D --> E{"超容?"} E -- 是 --> F["删尾, map.remove"] E -- 否 --> G["完成"] F --> G 
class LRUCache {
    class Node {
        int key, val; Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
    private final Map<Integer, Node> map = new HashMap<>();
    private final int cap;
    private final Node head = new Node(0,0), tail = new Node(0,0); // dummy 头尾

    public LRUCache(int capacity) {
        cap = capacity;
        head.next = tail; tail.prev = head;
    }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node n = map.get(key);
        moveToHead(n);
        return n.val;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node n = map.get(key);
            n.val = value; moveToHead(n);
        } else {
            Node n = new Node(key, value);
            map.put(key, n); addToHead(n);
            if (map.size() > cap) {
                Node last = tail.prev;
                removeNode(last);
                map.remove(last.key); // 节点必须存 key 才能删 map
            }
        }
    }
    void addToHead(Node n) {
        n.next = head.next; head.next.prev = n;
        head.next = n; n.prev = head;
    }
    void removeNode(Node n) {
        n.prev.next = n.next; n.next.prev = n.prev;
    }
    void moveToHead(Node n) { removeNode(n); addToHead(n); }
}

[!info] 复杂度
get/put 均 O(1)。

[!warning] 易错点

  • 节点必须存 key：淘汰尾节点时，需要知道它的 key 才能从哈希删。只存 val 会删不掉哈希项。
  • 顺序：先 removeNode 再 addToHead，别直接改指针。dummy 头尾让"头是最近、尾是最久"的语义稳定。

[!tip] 关联

  • 这是"哈希 + 双向链表"组合的经典，[[#460. LFU 缓存]] 是进阶版（加频次）。Java 自带的 LinkedHashMap（访问序）几行就能实现 LRU，但面试要求手写双向链表以考察原理。

8. 二叉树

树题的灵魂是递归。掌握一个通用框架，绝大多数题都能套：

[!tip] 递归三部曲

  1. 边界条件：root == null 时返回什么。
  2. 单层逻辑：假设左右子树已经递归出正确结果，当前层怎么用它们算出自己的结果。
  3. 返回值：把什么向上传递给父节点。

第二步的"假设子树已正确"是关键——别试图展开整棵树，只关心一层。这是分治思想。

另外要分清两种遍历：

  • DFS（递归/栈）：求深度、路径、祖先类问题。
  • BFS（队列层序）：按层处理、最短步数类问题。

94. 二叉树的中序遍历

返回中序遍历结果。

思路脉络：递归三行最简。但要会迭代法——用显式栈模拟递归，面试常考。

迭代法精髓：一路向左压栈到底，弹出访问，再转向右子树重复。这模拟了"左→根→右"的访问顺序。

graph LR A["一路向左压栈"] --> B["到底弹出访问"] B --> C["转向右子树"] C --> A 
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> st = new ArrayDeque<>();
        while (root != null || !st.isEmpty()) {
            while (root != null) { st.push(root); root = root.left; } // 左到底
            root = st.pop();   // 根
            res.add(root.val);
            root = root.right; // 右
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!tip] 套路

  • 前序迭代：访问放在"压栈时"而非"弹出时"。
  • 后序迭代：前序的"根左右"改成"根左右"再反转，或用 prev 标记右子是否已访问。

104. 二叉树的最大深度

求最大深度。

思路脉络：递归三部曲最典型的应用。边界 null 返回 0；单层 = max(左深度, 右深度) + 1；返回该层深度。

class Solution {
    public int maxDepth(TreeNode root) {
        return root == null ? 0
             : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!tip] 辨析

  • "最大深度"="高度"，从根到最远叶子。这题递归是后序（先算左右再算自己）。也可 BFS 层数层数，但递归更简洁。

226. 翻转二叉树

镜像翻转整棵树。

思路脉络：每个节点交换左右子，递归处理。这题是递归思维的入门——不关心整体怎么翻，只管"我这一层交换左右，剩下交给递归"。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode t = root.left; root.left = root.right; root.right = t;
        invertTree(root.left); invertTree(root.right);
        return root;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

101. 对称二叉树

判断树是否关于根轴对称。

思路脉络：不能单独看一棵子树，要两个指针比：左子树的左 vs 右子树的右，左子树的右 vs 右子树的左。这是"双指针"思想在树上的迁移。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }
    boolean check(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false; // 一空一非空
        return a.val == b.val
            && check(a.left, b.right)    // 镜像侧
            && check(a.right, b.left);
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!warning] 易错点

  • 先判"双 null"再判"单 null"，顺序反了会漏判。这是所有"两树对比"题的标准开头。

543. 二叉树的直径

任意两节点间最长路径的长度（边数）。

思路脉络：最长路径一定经过某个"最高点"节点，长度 = 该节点左深度 + 右深度（两侧各往下延伸）。后序遍历每个节点，用"左深度+右深度"更新全局答案，返回单边最大深度给上层。

注意：直径是边数，左深度 + 右深度 正好是边数（深度即从该点到子叶的边数）。

class Solution {
    int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return ans;
    }
    int depth(TreeNode root) {
        if (root == null) return 0;
        int l = depth(root.left), r = depth(root.right);
        ans = Math.max(ans, l + r);          // 经过当前节点的直径
        return Math.max(l, r) + 1;            // 返回单边深度给上层
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!warning] 易错点

  • 返回给上层的是 单边最大（max(l,r)+1），因为路径不能分叉往上走。但更新答案用两边和（l+r）。这两个用途要分清。

102. 二叉树的层序遍历

自顶向下一层一层返回节点值。

思路脉络：BFS 标准模板。关键是每层开始时记录队列长度 size，正好是这一层的节点数，按这个数循环出队入队，就把层切开了。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();              // 本层节点数
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode n = q.poll();
                level.add(n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            res.add(level);
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!tip] 套路

  • 这套 BFS 模板是 [[#199. 二叉树的右视图]]、[[#103. 二叉树的锯齿形层序遍历]]、[[#107. 自底向上的层序遍历]] 的基底，改的只是"每层怎么收集"。

108. 将有序数组转换为二叉搜索树

升序数组构造高度平衡 BST。

思路脉络：BST 中序是升序。要平衡，每次取中间元素作根，左半递归造左子，右半造右子。分治。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int m = (l + r) / 2;
        TreeNode root = new TreeNode(nums[m]);
        root.left = build(nums, l, m - 1);
        root.right = build(nums, m + 1, r);
        return root;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(log n)。

[!warning] 易错点

  • 左半是 [l, m-1]、右半是 [m+1, r]，m 本身已用作根，别带进去。l > r 是终止（不是 l >= r，否则单元素建不出节点）。

98. 验证二叉搜索树

判断是否合法 BST。

思路脉络：常见误区是只比"左 < 根 < 右"——这是局部正确，但 BST 要求整棵左子树都 < 根，只比直接子节点不够（如 5 / 4 6 / 3，3 比 6 小但比 5 小也合法的位置错了）。

正确做法：递归传递上下界 (lo, hi)，每个节点必须落在 (lo, hi) 内，进入左子收紧上界为当前值，进入右子收紧下界。用 long 避免整型极值越界。

graph LR A["节点 root, 界 (lo,hi)"] --> B{"lo < val < hi?"} B -- 否 --> C["返回 false"] B -- 是 --> D["左子 (lo, val)"] D --> E["右子 (val, hi)"] 
class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    boolean check(TreeNode root, long lo, long hi) {
        if (root == null) return true;
        if (root.val <= lo || root.val >= hi) return false;
        return check(root.left, lo, root.val) && check(root.right, root.val, hi);
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!tip] 另解

  • 中序遍历应是严格递增，边遍历边比前驱。也是 O(n)，但上下界法更直观体现 BST 语义。

230. 二叉搜索树中第 K 小的元素

BST 中找第 K 小。

思路脉络：BST 的中序遍历是升序，第 K 小就是中序第 K 个。递归中序遍历，用一个计数器数到第 K 个即停。比遍历完整棵再取第 K 个更高效——可提前终止。

class Solution {
    int k, ans;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return ans;
    }
    void dfs(TreeNode root) {
        if (root == null || k == 0) return;  // k==0 表示已找到, 剪枝
        dfs(root.left);
        if (--k == 0) { ans = root.val; return; }
        dfs(root.right);
    }
}

[!info] 复杂度
时间 O(h+k)，空间 O(h)。

[!tip] 套路

  • "BST + 第 K 大/小" 一律中序。第 K 大用逆中序（右→根→左）。

199. 二叉树的右视图

从右侧看树，从上到下返回每层最右可见节点。

思路脉络：层序遍历，每层最后一个节点就是右视图看到的。复用 [[#102. 二叉树的层序遍历]] 模板，只把"每层最后一个"加入结果。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode n = q.poll();
                if (i == size - 1) res.add(n.val); // 每层最后一个
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!tip] 另解

  • DFS 优先走右子，记录"每层第一个被访问的节点"——即该层最右。空间 O(h) 更省，但层序更直观。

114. 二叉树展开为链表

按前序遍历把树展开成右链（每个节点只有右孩子）。

思路脉络：两种经典法。

递归后序法（右→左→中）：维护全局 prev 指向上一个处理的节点。后序保证处理当前节点时左右子已展平。把 root.right = prev、root.left = null，再 prev = root。逆前序的访问顺序恰好让链表从尾向头接起来。

O(1) 空间法：对每个有左子的节点，把左子树的最右节点接到当前右子前，再把左子整体移到右边、左置空。

graph LR A["后序: 右→左→中"] --> B["处理 root 时, prev 已是右链头"] B --> C["root.right = prev"] C --> D["root.left = null"] D --> E["prev = root"] 
class Solution {
    TreeNode prev = null;
    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);  // 先右
        flatten(root.left);   // 再左
        root.right = prev;    // 接上已展平的链
        root.left = null;
        prev = root;          // 自己成为下一个的前驱
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)（递归栈）。

[!warning] 易错点

  • 必须先 flatten(right) 再 flatten(left)，否则 prev 顺序错乱。本质是模拟"前序的逆序"：前序是中左右，逆过来是右左中。

105. 从前序与中序遍历序列构造二叉树

给前序和中序，构造原二叉树。

思路脉络：前序第一个是根。在中序里找到根的位置，左边是左子树、右边是右子树。递归构造左右子树。

关键优化：中序里"找根位置"用哈希 O(1)，否则每次扫描 O(n)。前序用一个全局下标 i 顺序取根——因为前序天然是"根→左子所有→右子所有"，按顺序取并与中序的区间对应。

graph LR A["前序取根 preorder[i++]"] --> B["中序找根位置 m"] B --> C["左子: 中序 l..m-1"] C --> D["右子: 中序 m+1..r"] D --> E["返回 root"] 
class Solution {
    int[] preorder; int i = 0;
    Map<Integer, Integer> idx = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int j = 0; j < inorder.length; j++) idx.put(inorder[j], j);
        return build(0, inorder.length - 1);
    }
    TreeNode build(int l, int r) {
        if (l > r) return null;
        int val = preorder[i++];            // 顺序取前序根
        int m = idx.get(val);                // 中序定位
        TreeNode root = new TreeNode(val);
        root.left = build(l, m - 1);         // 左子对应中序左半
        root.right = build(m + 1, r);        // 右子对应中序右半
        return root;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

  • 前序 i 是全局递增的，左子树构造完 i 会自动走到右子树对应的根——这依赖"先建左子再建右子"的顺序，顺序反了 i 就错位。

437. 路径总和 III

找树中所有"向下路径"和等于 targetSum 的条数。节点值可负。

思路脉络：这是 [[#560. 和为 K 的子数组]] 的树上版——前缀和 + 哈希。从根到当前节点累积一条前缀和 sum，问有多少个祖先的前缀和等于 sum - target，就有多少条以当前节点结尾的合法路径。

关键差异：树有多条分支，前缀和哈希要在回溯时撤销当前节点的贡献——因为退出当前分支后，它的前缀和不再属于其它分支的祖先链。这是和数组版最大的区别。

class Solution {
    int ans = 0, target;
    Map<Long, Integer> cnt = new HashMap<>();
    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        cnt.put(0L, 1);                    // 前缀和 0 出现 1 次
        dfs(root, 0L);
        return ans;
    }
    void dfs(TreeNode root, long sum) {
        if (root == null) return;
        sum += root.val;
        ans += cnt.getOrDefault(sum - target, 0);
        cnt.merge(sum, 1, Integer::sum);    // 加入当前前缀和
        dfs(root.left, sum);
        dfs(root.right, sum);
        cnt.merge(sum, -1, Integer::sum);  // 回溯撤销!
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

  • 回溯撤销是这题灵魂。不撤销会把兄弟分支的前缀和也算进来，导致路径不连续。targetSum 用 long 防溢出。

236. 二叉树的最近公共祖先

找两个节点 p、q 在树中的最近公共祖先。

思路脉络：递归的语义要先定义清楚——lca(root) 返回"以 root 为根的子树里 p、q 的祖先情况"：

  • 找到 p 或 q（含 root 自身）就返回该节点；
  • 左右子树各返回非 null，说明 p、q 分居两侧，当前 root 就是 LCA；
  • 只一侧非 null，说明 p、q 都在那侧（或那侧找到的本身就是另一个的祖先），返回那侧。

[!example] 后序递归找 LCA（动图）
找 p=5、q=4：后序深入，命中 p 直接返回自身；左右都非空→当前是 LCA；单边非空→透传那侧。本例 5 自身就是 p 且是 q 的祖先，命中即返回，5 就是 LCA。

0236-lca

graph LR A["root==null/p/q?"] --> B["返回 root"] B --> C["递归左 l, 递归右 r"] C --> D{"l 和 r 都非空?"} D -- 是 --> E["root 就是 LCA"] D -- "只 l 非空" --> F["返回 l"] D -- "只 r 非空" --> G["返回 r"] 
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        if (l != null && r != null) return root; // 分居两侧
        return l != null ? l : r;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!tip] 妙处

  • 这套递归巧妙处理了"p 是 q 祖先"的情况：找到 p 时直接返回 p，上层一侧非空一侧空，返回 p，p 自然就是 LCA。无需特判。

124. 二叉树中的最大路径和

找树中任意路径（节点序列，可不经过根）的最大和。

思路脉络：定义"贡献"——gain(root) 返回从 root 向下一侧延伸能获得的最大和（负贡献截断为 0，因为不走比走负数更好）。

每经过一个节点，以它为"最高点"的路径和 = 左贡献 + 右贡献 + 自身，用它更新答案。但返回给父节点的只能是单边（路径不能分叉），所以返回 max(左贡献, 右贡献) + 自身。

graph LR A["gain(root)"] --> B["左贡献=max(0, gain(left))"] B --> C["右贡献=max(0, gain(right))"] C --> D["ans=max(ans, 左+右+root.val)"] D --> E["返回 max(左,右)+root.val 给上层"] 
class Solution {
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        gain(root);
        return ans;
    }
    int gain(TreeNode root) {
        if (root == null) return 0;
        int l = Math.max(0, gain(root.left));  // 负贡献截断
        int r = Math.max(0, gain(root.right));
        ans = Math.max(ans, l + r + root.val); // 经过当前的完整路径
        return Math.max(l, r) + root.val;       // 单边向上贡献
    }
}

[!info] 复杂度
时间 O(n)，空间 O(h)。

[!warning] 易错点

  • ans 用"两边和"（完整路径可分叉在当前节点），return 用"单边"（向上不能分叉）。这是和 [[#543. 二叉树的直径]] 完全同构的思路——一个记和、一个记边数，框架一致。

[!tip] 关联

  • [[#543. 二叉树的直径]]、[[#124. 二叉树中的最大路径和]]、[[#687. 最长同值路径]] 是一族"后序 + 全局答案 + 单边返回"题，套路完全一致，掌握一个其余即通。

9. 图论

图论的四把刀：

  1. DFS 染色：连通分量、感染扩散，递归标记。
  2. BFS 层序：最短步数、多源同时扩散，队列按层处理。
  3. 拓扑排序：依赖关系、有向无环判定，入度表 + BFS。
  4. Trie：字符串前缀检索，多叉树。

200. 岛屿数量

1 是陆地、0 是水，数岛屿数（四连通的 1 算一岛）。

思路脉络：遍历每个格子，遇到 1 就是一个新岛——DFS 把整片连通的 1 全染成 0（原地标记"已访问"），计数加一。原地修改省去 visited 数组。

graph LR A["遍历 grid"] --> B{"是 '1'?"} B -- 是 --> C["DFS 感染整岛为 '0'"] C --> D["ans++"] B -- 否 --> A D --> A 
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length, ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == '1') { dfs(grid, i, j); ans++; }
        return ans;
    }
    void dfs(char[][] g, int i, int j) {
        if (i < 0 || i >= g.length || j < 0 || j >= g[0].length || g[i][j] != '1') return;
        g[i][j] = '0';                                    // 原地标记
        dfs(g, i+1, j); dfs(g, i-1, j); dfs(g, i, j+1); dfs(g, i, j-1);
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(mn)（最坏递归栈）。

[!tip] 变形

  • 八连通改 4 个方向为 8 个。求岛屿面积就 DFS 返回计数。求最大岛可先标记再统计。

994. 腐烂的橘子

每分钟烂橘子感染四邻新鲜橘子，求全部腐烂的最短时间，不可能返回 -1。

思路脉络：经典多源 BFS。初始所有烂橘子同时入队（它们都是第 0 层），按层扩散，层数就是分钟数。过程中统计新鲜橘子数 fresh，全腐烂即 fresh==0。

[!example] 多源 BFS 按层扩散（动图）
3×3 网格：初始烂橘子(0,0)同时入队为第0层，每分钟感染四邻、按层推进，层数即分钟数。本例 4 分钟全烂。若最后 fresh>0 返回 -1。

0994-oranges

graph LR A["所有烂橘子同时入队"] --> B["按层 BFS 扩散"] B --> C["感染邻居, fresh--"] C --> D["层数++"] D --> E{"fresh==0?"} E -- 是 --> F["返回层数"] E -- 否 --> B F2["队列空仍 fresh>0"] --> G["返回 -1"] 
class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length, fresh = 0;
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) q.offer(new int[]{i, j});
                else if (grid[i][j] == 1) fresh++;
            }
        int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
        int min = 0;
        while (!q.isEmpty() && fresh > 0) {       // fresh>0 才继续, 否则多算一层
            for (int k = q.size(); k > 0; k--) {
                int[] c = q.poll();
                for (int[] dir : d) {
                    int x = c[0]+dir[0], y = c[1]+dir[1];
                    if (x<0||x>=m||y<0||y>=n||grid[x][y]!=1) continue;
                    grid[x][y] = 2; fresh--;
                    q.offer(new int[]{x, y});
                }
            }
            min++;
        }
        return fresh == 0 ? min : -1;
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(mn)。

[!warning] 易错点

  • 循环条件带 fresh > 0：避免最后一层已无新鲜橘子时多加一分钟。
  • 初始就 fresh==0（没有新鲜橘子）应返回 0，上面写法天然满足。

207. 课程表

n 门课，prerequisites[i]=[a,b] 表示先修 b 再修 a。判断能否修完。

思路脉络：建图后就是拓扑排序——能否把所有节点排成无冲突顺序，等价于图无环。

BFS 做法：建入度表，入度为 0 的先入队，每次出队并把其后继入度减一，新的 0 入队。最后看处理的节点数是否等于 n。

graph LR A["建图 + 入度表"] --> B["入度 0 的入队"] B --> C["出队, 后继入度--"] C --> D{"新的入度 0?"} D -- 是 --> E["入队"] D -- 否 --> C E --> C C --> F{"处理数 == n?"} F -- 是 --> G["可完成(无环)"] F -- 否 --> H["有环, 不可"] 
class Solution {
    public boolean canFinish(int n, int[][] prerequisites) {
        List<List<Integer>> g = new ArrayList<>();
        int[] indeg = new int[n];
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] p : prerequisites) {           // p[1] -> p[0]
            g.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
        int cnt = 0;
        while (!q.isEmpty()) {
            int c = q.poll(); cnt++;
            for (int nx : g.get(c)) if (--indeg[nx] == 0) q.offer(nx);
        }
        return cnt == n;                          // 全部排完则无环
    }
}

[!info] 复杂度
时间 O(V+E)，空间 O(V+E)。

[!warning] 易错点

  • 边方向别建反：[a,b] 表示"先 b 后 a"，所以是 b→a（b 是 a 的前驱，a 依赖 b，b 完成后 a 入度才减）。建反了入度语义就错。

208. 实现 Trie (前缀树)

实现 insert、search、startsWith。

思路脉络：Trie 是一棵 26 叉树，每条边代表一个字母。共享前缀的词共用路径，省空间。每个节点有 children[26] 和 isEnd 标记"是否有词在此结束"。

  • search 要求整条路径存在且终点 isEnd。
  • startsWith 只要求路径存在，不要求 isEnd。
graph LR A["root"] --> B["按字符逐层下走"] B --> C{"children 存在?"} C -- 是 --> B C -- 否 --> D["新建节点"] D --> B B --> E["末尾置 isEnd (insert)"] 
class Trie {
    private Trie[] children = new Trie[26];
    private boolean isEnd;
    public Trie() {}
    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) node.children[i] = new Trie();
            node = node.children[i];
        }
        node.isEnd = true;
    }
    public boolean search(String word) {
        Trie node = walk(word);
        return node != null && node.isEnd;
    }
    public boolean startsWith(String prefix) {
        return walk(prefix) != null;
    }
    private Trie walk(String s) {
        Trie node = this;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) return null;
            node = node.children[i];
        }
        return node;
    }
}

[!info] 复杂度
insert/search/startsWith 均 O(L)（L 为串长），空间 O(总字符数)。

[!tip] 价值

  • Trie 把"前缀匹配"从 O(总词数 × 词长) 降到 O(前缀长)。自动补全、词典检索、IP 路由都靠它。walk 抽出来复用是这题的整洁写法。

10. 回溯

回溯是"带撤销的 DFS"。所有"枚举所有方案"的题——排列、组合、子集、分割、棋盘——都能套一个框架：

void backtrack(路径, 选择列表):
    if 满足结束条件: 收集结果; return
    for 选择 in 选择列表:
        做选择          // 加入路径、标记
        backtrack(...)
        撤销选择         // 移除路径、取消标记

[!tip] 三要素

  1. 结束条件：路径满了/达到约束。
  2. 选择列表：当前位置能选什么。排列用 used 数组，组合/子集用 start 去重。
  3. 撤销：和"做选择"严格对称。add 配 remove、true 配 false、append 配 deleteCharAt。

区分排列 vs 组合的关键：排列要顺序（[1,2]≠[2,1]），组合不要顺序。所以排列每层从头扫（用 used 跳过已选），组合用 start 保证只往后选（避免同集合不同序）。

46. 全排列

返回无重复数组的所有全排列。

思路脉络：排列的经典。用 used 数组标记已选，每层从头扫跳过已用的。结束条件是路径长度等于数组长度。

[!example] 回溯搜索树（动图）
[1,2,3]：每层枚举未用数，做选择→递归→撤销。路径满(长度=n)收集。撤销让同一路径变量被复用。n=3 共 3!=6 个全排列。

0046-permutations

graph LR A["选一个未用数"] --> B["加入路径, used=true"] B --> C["递归"] C --> D{"路径满?"} D -- 是 --> E["收集结果"] D -- 否 --> A E --> F["撤销: remove, used=false"] F --> A 
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backtrack(nums, new ArrayList<>(), new boolean[nums.length]);
        return res;
    }
    void backtrack(int[] nums, List<Integer> path, boolean[] used) {
        if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.add(nums[i]); used[i] = true;
            backtrack(nums, path, used);
            path.remove(path.size() - 1); used[i] = false; // 撤销
        }
    }
}

[!info] 复杂度
时间 O(n·n!)，空间 O(n)。

[!warning] 易错点

  • 收集时要 new ArrayList<>(path) 复制，不能直接 add(path)——path 是同一个引用，回溯后会被清空，最终结果全空。

78. 子集

返回无重复数组的所有子集。

思路脉络：子集的特别之处：每个递归节点都是一个合法子集（不只是叶子）。所以收集放在进入函数时，而非结束条件里。用 start 控制只往后选，保证不重复。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0, new ArrayList<>());
        return res;
    }
    void backtrack(int[] nums, int start, List<Integer> path) {
        res.add(new ArrayList<>(path));           // 每个节点都是子集
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path);
            path.remove(path.size() - 1);
        }
    }
}

[!info] 复杂度
时间 O(n·2ⁿ)，空间 O(n)。

[!tip] 套路

  • "收集在每个节点" vs "收集在叶子"：子集类前者，排列/组合类后者。这个区别决定 res.add 放在哪。

17. 电话号码的字母组合

数字串（如 "23"）映射到字母组合。

思路脉络：每个数字对应一组字母，求笛卡尔积。回溯按数字位置 idx 推进，每层选当前数字对应的一个字母。StringBuilder 的撤销是 deleteCharAt。

class Solution {
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) return res;
        backtrack(digits, 0, new StringBuilder());
        return res;
    }
    void backtrack(String digits, int idx, StringBuilder sb) {
        if (idx == digits.length()) { res.add(sb.toString()); return; }
        for (char c : map[digits.charAt(idx) - '0'].toCharArray()) {
            sb.append(c);
            backtrack(digits, idx + 1, sb);
            sb.deleteCharAt(sb.length() - 1);     // 撤销
        }
    }
}

[!info] 复杂度
时间 O(4ⁿ)（最坏每个数字 4 字母），空间 O(n)。

[!warning] 易错点

  • map[0]、map[1] 是空串（数字 0/1 无对应字母）。空输入直接返回空列表，别误返回含空串的列表。

39. 组合总和

无重复正整数 candidates，找所有和为 target 的组合，元素可无限次使用。

思路脉络：回溯，remain 跟踪剩余目标。元素可重复用，所以递归时 start 传 i（不是 i+1）。排序后可剪枝：当前候选 > remain 就 break（后面的更大）。

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] c, int target) {
        Arrays.sort(c);                            // 剪枝前提
        backtrack(c, target, 0, new ArrayList<>());
        return res;
    }
    void backtrack(int[] c, int remain, int start, List<Integer> path) {
        if (remain == 0) { res.add(new ArrayList<>(path)); return; }
        for (int i = start; i < c.length; i++) {
            if (c[i] > remain) break;               // 排序后剪枝
            path.add(c[i]);
            backtrack(c, remain - c[i], i, path);   // i 不+1, 可重复用
            path.remove(path.size() - 1);
        }
    }
}

[!info] 复杂度
时间取决于组合数，最坏 O(2ⁿ) 级别，空间 O(target/min)。

[!tip] 辨析

  • "元素可重复用"→递归传 i；"每个用一次"→传 i+1（[[#40. 组合总和 II]]）；"含重复元素去重"→排序后跳过相邻重复（[[#90. 子集 II]] 同理）。

22. 括号生成

生成 n 对括号的所有合法组合。

思路脉络：回溯时跟踪两个计数：已用左括号 open、已用右括号 close。两条规则保证合法：

  • open < n：还能放左括号。
  • close < open：只有左括号比右括号多时才能放右括号（否则会先闭后开，非法）。
graph LR A["sb, open, close"] --> B{"open < n?"} B -- 是 --> C["放 (, open++"] C --> A B -- 否 --> D{"close < open?"} D -- 是 --> E["放 ), close++"] E --> A D -- 否 --> F{"len == 2n?"} F -- 是 --> G["收集"] 
class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        backtrack(new StringBuilder(), 0, 0, n);
        return res;
    }
    void backtrack(StringBuilder sb, int open, int close, int n) {
        if (sb.length() == 2 * n) { res.add(sb.toString()); return; }
        if (open < n)  { sb.append('('); backtrack(sb, open + 1, close, n); sb.deleteCharAt(sb.length() - 1); }
        if (close < open) { sb.append(')'); backtrack(sb, open, close + 1, n); sb.deleteCharAt(sb.length() - 1); }
    }
}

[!info] 复杂度
时间 O(4ⁿ/√n)（卡特兰数），空间 O(n)。

[!warning] 易错点

  • close < open 是合法性的核心：右括号必须匹配一个已放的左括号。写成 close < n 会生成 )( 这种非法串。

79. 单词搜索

在二维字符网格中搜索单词（上下右左连通），字母不可重复用。

思路脉络：每个格子都可能作起点，DFS 四向扩展。关键在回溯标记：进入格子先改成 #（或 visited）防止重复用，退出时恢复——这是回溯的"撤销"在网格题的体现。

graph LR A["每个格子作起点"] --> B["DFS 匹配 word[k]"] B --> C{"匹配?"} C -- 是 --> D["标记 # "] D --> E["四向 DFS k+1"] E --> F["恢复原字符 撤销"] F --> G{"任一方向成功?"} C -- 否 --> H["回退 false"] G -- 是 --> I["返回 true"] G -- 否 --> H 
class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (dfs(board, word, i, j, 0)) return true;
        return false;
    }
    boolean dfs(char[][] b, String w, int i, int j, int k) {
        if (k == w.length()) return true;                       // 匹配完
        if (i<0||i>=b.length||j<0||j>=b[0].length||b[i][j]!=w.charAt(k)) return false;
        char t = b[i][j]; b[i][j] = '#';                        // 标记
        boolean f = dfs(b,w,i+1,j,k+1)||dfs(b,w,i-1,j,k+1)
                  ||dfs(b,w,i,j+1,k+1)||dfs(b,w,i,j-1,k+1);
        b[i][j] = t;                                            // 撤销
        return f;
    }
}

[!info] 复杂度
时间 O(mn·3ᴸ)（每步最多 3 个新方向，L 是词长），空间 O(L)。

[!warning] 易错点

  • 标记和恢复必须配对：用 char t 存原值，DFS 后 b[i][j]=t 还原。漏恢复会让其他起点的搜索踩到 # 而误判。

131. 分割回文串

把字符串切成若干子串，每个子串都是回文，返回所有切法。

思路脉络：回溯切分位置。从 start 起，枚举分割点 end，若 [start,end] 是回文就切下来递归处理 end+1 起。start == n 时收集一组完整分割。

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtrack(s, 0, new ArrayList<>());
        return res;
    }
    void backtrack(String s, int start, List<String> path) {
        if (start == s.length()) { res.add(new ArrayList<>(path)); return; }
        for (int end = start; end < s.length(); end++) {
            if (!isP(s, start, end)) continue;       // 非回文就跳过
            path.add(s.substring(start, end + 1));
            backtrack(s, end + 1, path);
            path.remove(path.size() - 1);
        }
    }
    boolean isP(String s, int l, int r) {
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
}

[!info] 复杂度
时间 O(n·2ⁿ)，空间 O(n)。

[!tip] 优化

  • 预处理 dp[i][j] 回文表（O(n²)），回溯时 O(1) 查询，避免每次双指针判回文。对长串显著提速。

51. N 皇后

在 n×n 棋盘放 n 个皇后，互不攻击（同行同列同对角线），返回所有摆法。

思路脉络：逐行回溯，每行选一列放皇后。冲突检查只需看上方（同行只放一个、下方还没放）：同列、左上对角、右上对角。

graph LR A["逐行 row"] --> B["枚举列 col"] B --> C{"不冲突?"} C -- 是 --> D["放 Q"] D --> E["递归 row+1"] E --> F["撤销, 放 ."] F --> B C -- 否 --> B E --> G{"row == n?"} G -- 是 --> H["收集棋盘"] 
class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] b = new char[n][n];
        for (char[] r : b) Arrays.fill(r, '.');
        backtrack(b, 0);
        return res;
    }
    void backtrack(char[][] b, int row) {
        if (row == b.length) { res.add(build(b)); return; }
        for (int col = 0; col < b.length; col++) {
            if (!valid(b, row, col)) continue;
            b[row][col] = 'Q';
            backtrack(b, row + 1);
            b[row][col] = '.';                    // 撤销
        }
    }
    boolean valid(char[][] b, int r, int c) {
        for (int i = 0; i < r; i++) if (b[i][c] == 'Q') return false;        // 同列
        for (int i=r-1,j=c-1; i>=0&&j>=0; i--,j--) if (b[i][j]=='Q') return false; // 左上对角
        for (int i=r-1,j=c+1; i>=0&&j<b.length; i--,j++) if (b[i][j]=='Q') return false; // 右上对角
        return true;
    }
    List<String> build(char[][] b) {
        List<String> l = new ArrayList<>();
        for (char[] r : b) l.add(new String(r));
        return l;
    }
}

[!info] 复杂度
时间 O(n!)（每行可选列递减），空间 O(n)。

[!tip] 优化

  • 用三个 Set 记录"已占列、主对角(row−col)、副对角(row+col)"，valid 降到 O(1)。对角线用 row−col、row+col 作 key 是经典技巧。

[!tip] 套路

  • N 皇后是回溯的"集大成者"：选位置→递归→撤销，加上约束剪枝。掌握它，[[#37. 解数独]]、[[#52. N 皇后 II]] 都是同模板。

11. 二分查找

二分的本质是在单调性上收缩边界：每次比较排除一半。难点不在二分本身，在边界处理——找精确值、找左界、找右界，三种目标的循环条件和收缩方式不同。

[!tip] 左闭右闭模板三态
统一用 [l, r] 左闭右闭，while (l <= r)：

  • 精确值：nums[m]==t 直接返回 m。
  • 左界（第一个 ==t）：命中也 r = m - 1 继续往左找，记录候选 ans，最后返回 l。
  • 右界（最后一个 ==t）：命中也 l = m + 1 继续往右找，最后返回 r。

记一句口诀：左界命中往左压，右界命中往右压。

35. 搜索插入位置

给有序数组找 target，找到返回下标，找不到返回应插入位置。

思路脉络：标准精确二分。找不到时，l 正好停在该插入的位置——因为循环结束时 l == r + 1，l 指向第一个大于 target 的位置。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target) return m;
            else if (nums[m] < target) l = m + 1;
            else r = m - 1;
        }
        return l;                        // 插入位置
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(1)。

[!tip] 套路

  • 这题是"左界"二分的简化版。把"找到返回"去掉，return l 就是">= target 的第一个位置"，正是插入位置。

74. 搜索二维矩阵

每行升序，且每行首大于上一行尾。找 target。

思路脉络：这种"行间也升序"的矩阵等价于一维升序数组——把 mid 映射到 matrix[mid/n][mid%n] 即可，一次二分搞定。别被二维外表骗了。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int l = 0, r = m * n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            int v = matrix[mid / n][mid % n];    // 一维下标转二维
            if (v == target) return true;
            else if (v < target) l = mid + 1;
            else r = mid - 1;
        }
        return false;
    }
}

[!info] 复杂度
时间 O(log mn)，空间 O(1)。

[!tip] 辨析

  • 注意和 [[#240. 搜索二维矩阵 II]] 区别：那题每行升、每列升但行间未必衔接，不能压成一维，得用右上角 O(m+n)。本题行间严格衔接，才能一维二分。

34. 在排序数组中查找元素的第一个和最后一个位置

找 target 在有序数组里的起止下标，没有返回 [-1,-1]。

思路脉络：两次二分，一次找左界、一次找右界。命中时不停，继续往对应方向压。

graph LR A["二分找左界"] --> B{"nums[m] == t?"} B -- 是 --> C["ans=m, r=m-1 往左压"] B -- "<t" --> D["l=m+1"] B -- ">t" --> E["r=m-1"] C --> A D --> A E --> A 
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findLeft(nums, target), findRight(nums, target)};
    }
    int findLeft(int[] a, int t) {
        int l = 0, r = a.length - 1, ans = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (a[m] == t) { ans = m; r = m - 1; }  // 命中往左压
            else if (a[m] < t) l = m + 1;
            else r = m - 1;
        }
        return ans;
    }
    int findRight(int[] a, int t) {
        int l = 0, r = a.length - 1, ans = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (a[m] == t) { ans = m; l = m + 1; }  // 命中往右压
            else if (a[m] < t) l = m + 1;
            else r = m - 1;
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(1)。

[!warning] 易错点

  • 找左界命中时 r = m - 1，找右界命中时 l = m + 1——方向反了会找错界。

33. 搜索旋转排序数组

升序数组在某个点旋转过（如 [4,5,6,7,0,1,2]），找 target，O(log n)。

思路脉络：旋转数组虽整体无序，但对 mid 切一刀，必有一半是有序的。判断哪半有序，再看 target 在不在那半的范围内，决定往哪边缩。

  • nums[l] <= nums[m]：左半有序。若 target 在 [nums[l], nums[m]) 内，搜左半；否则搜右半。
  • 否则右半有序。若 target 在 (nums[m], nums[r]] 内，搜右半；否则搜左半。
graph LR A["取 mid"] --> B{"nums[l] ≤ nums[m]?"} B -- 是, 左半有序 --> C{"target 在左半?"} C -- 是 --> D["r=mid-1"] C -- 否 --> E["l=mid+1"] B -- 否, 右半有序 --> F{"target 在右半?"} F -- 是 --> E F -- 否 --> D 
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (nums[m] == target) return m;
            if (nums[l] <= nums[m]) {                        // 左半有序
                if (nums[l] <= target && target < nums[m]) r = m - 1;
                else l = m + 1;
            } else {                                         // 右半有序
                if (nums[m] < target && target <= nums[r]) l = m + 1;
                else r = m - 1;
            }
        }
        return -1;
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(1)。

[!warning] 易错点

  • 判断"左半有序"用 nums[l] <= nums[m]（含等号，处理 l==m 的两元素情况）。范围判断用闭开区间 [nums[l], nums[m])，边界别漏。

153. 寻找旋转排序数组中的最小值

旋转过的升序数组（无重复）找最小值，O(log n)。

思路脉络：和 right 比。nums[m] > nums[r] 说明最小值在 mid 右侧（左半都比 nums[r] 大，不是最小）；否则最小值在 mid 或左侧。注意循环用 l < r，收缩 r = m（不是 m - 1），因为 mid 本身可能是最小值。

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (nums[m] > nums[r]) l = m + 1;   // 最小在右半
            else r = m;                          // 最小在 m 或左半
        }
        return nums[l];                          // l == r 即最小
    }
}

[!info] 复杂度
时间 O(log n)，空间 O(1)。

[!warning] 易错点

  • 和 right 比而不是 left：和 left 比无法区分"未旋转"和"旋转后最小在右"。r = m 不减一，因为 mid 可能就是答案。

4. 寻找两个正序数组的中位数

两个升序数组找中位数，O(log (m+n))。

思路脉络：中位数是"把合并数组平分两半的分界点"。不合并，而是二分较短数组的划分数，让左半元素总数等于 (m+n+1)/2。

设 a 短、b 长。在 a 上二分切 i 个到左半，则 b 切 j = half - i 个。合法划分要满足：a 左最大 aL <= bR 且 b 左最大 bL <= aR。

  • 满足：找到划分。奇数取 max(aL, bL)，偶数取 (max(aL,bL) + min(aR,bR))/2。
  • aL > bR：a 切多了，hi = i - 1。
  • 否则 a 切少了，lo = i + 1。

边界用 ±∞ 处理一侧切空的情况。

graph LR A["二分 a 的切点 i"] --> B["j = half - i"] B --> C["aL,aR,bL,bR"] C --> D{"aL ≤ bR 且 bL ≤ aR?"} D -- 是 --> E["合法划分, 算中位数"] D -- "aL>bR" --> F["hi=i-1"] D -- "bL>aR" --> G["lo=i+1"] F --> A G --> A 
class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        if (a.length > b.length) return findMedianSortedArrays(b, a); // 保证 a 短
        int m = a.length, n = b.length, half = (m + n + 1) / 2;
        int lo = 0, hi = m;
        while (lo <= hi) {
            int i = (lo + hi) / 2, j = half - i;
            int aL = i == 0 ? Integer.MIN_VALUE : a[i - 1];
            int aR = i == m ? Integer.MAX_VALUE : a[i];
            int bL = j == 0 ? Integer.MIN_VALUE : b[j - 1];
            int bR = j == n ? Integer.MAX_VALUE : b[j];
            if (aL <= bR && bL <= aR) {
                if ((m + n) % 2 == 1) return Math.max(aL, bL);
                return (Math.max(aL, bL) + Math.min(aR, bR)) / 2.0;
            } else if (aL > bR) hi = i - 1;
            else lo = i + 1;
        }
        return 0;
    }
}

[!info] 复杂度
时间 O(log(min(m,n)))，空间 O(1)。

[!warning] 易错点

  • 必须在短数组上二分：否则 j = half - i 可能越界（长数组切太多导致 j 为负）。开头的 swap 保证 a 短。
  • 边界用 ±∞：i==0 时 aL 取 MIN_VALUE，保证 max(aL,bL) 永远是另一边的真实值。漏了会数组越界。

12. 栈

栈的两类典型：

  1. 匹配/消除：括号配对、字符串解码，遇同类闭合就弹出。
  2. 单调栈：求"下一个更大/更小"，维护单调性，弹栈时计算答案。

单调栈的精髓：栈里存下标（不是值），弹栈时由"被弹元素"和"触发弹出的元素"配对出答案。

20. 有效的括号

判断括号串是否合法（()[]{} 闭合且顺序正确）。

思路脉络：遇左括号入栈，遇右括号检查栈顶是否是对应左括号——是则弹，否则非法。最后栈空才合法。用 Map 存右→左映射，简化匹配。

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> m = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (!m.containsKey(c)) st.push(c);          // 左括号入栈
            else if (st.isEmpty() || st.pop() != m.get(c)) return false; // 右括号配对
        }
        return st.isEmpty();                            // 栈空才合法
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

  • 右括号配对前先判栈空：形如 ] 开头，栈空直接 pop 会异常。st.pop() != m.get(c) 复用短路，但前面要先查 isEmpty。

155. 最小栈

栈支持 push/pop/top/getMin 全 O(1)。

思路脉络：单栈无法 O(1) 取最小。辅助栈 minSt 同步压栈，每步记录"当前栈内最小值"。pop 时两栈同步弹。空间 O(n)。

class MinStack {
    Deque<Integer> st = new ArrayDeque<>(), minSt = new ArrayDeque<>();
    public MinStack() { minSt.push(Integer.MAX_VALUE); }
    public void push(int v) { st.push(v); minSt.push(Math.min(minSt.peek(), v)); }
    public void pop() { st.pop(); minSt.pop(); }
    public int top() { return st.peek(); }
    public int getMin() { return minSt.peek(); }
}

[!info] 复杂度
各操作 O(1)，空间 O(n)。

[!tip] 优化

  • O(1) 空间做法：存差值 v - min。但辅助栈法最直观、不易错，面试首选。

394. 字符串解码

3[a2[c]] → accaccacc，数字表示重复次数。

思路脉络：遇数字攒次数、遇 [ 把当前串和次数压栈并重置、遇 ] 弹栈拼接。两个栈分别存"外层串"和"重复次数"，[ 时入栈、] 时出栈。

graph LR A["遍历字符"] --> B{"类型?"} B -- 数字 --> C["攒成完整数"] B -- 字母 --> D["拼到 cur"] B -- "[ " --> E["压栈 cur, num; 重置"] B -- "]" --> F["弹出 prev, k; cur=prev+cur×k"] 
class Solution {
    public String decodeString(String s) {
        Deque<String> strSt = new ArrayDeque<>();
        Deque<Integer> numSt = new ArrayDeque<>();
        StringBuilder cur = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) num = num * 10 + (c - '0');
            else if (c == '[') { strSt.push(cur.toString()); numSt.push(num); cur = new StringBuilder(); num = 0; }
            else if (c == ']') {
                int k = numSt.pop();
                StringBuilder prev = new StringBuilder(strSt.pop());
                for (int i = 0; i < k; i++) prev.append(cur);
                cur = prev;
            } else cur.append(c);
        }
        return cur.toString();
    }
}

[!info] 复杂度
时间 O(输出长度)，空间 O(嵌套深度)。

[!warning] 易错点

  • 数字可能多位（如 12[a]），必须 num*10 + c-'0' 攒完整数。[ 时重置 num=0 和 cur，] 时用 prev 包裹 cur 重复 k 次。

739. 每日温度

每天温度，问要等几天才出现更高温度，没有填 0。

思路脉络：单调栈经典。维护递减栈（存下标）：当天比栈顶高，栈顶出栈，答案 = 当前下标 − 栈顶下标。栈里剩下的没人更高，答案 0。

[!example] 单调递减栈弹栈结算（动图）
[73,74,75,71,69,72,76,73]：遇更高温弹栈，ans=当前下标−栈顶下标。递减段连续入栈不结算，升温时连续弹栈结算。末栈未结算填 0。结果 [1,1,4,2,1,1,0,0]。

0739-daily-temp

graph LR A["遍历 i, t"] --> B{"栈非空且 t > 栈顶温度?"} B -- 是 --> C["弹 top, ans=top = i - top"] C --> B B -- 否 --> D["i 入栈"] D --> A 
class Solution {
    public int[] dailyTemperatures(int[] T) {
        int n = T.length, res[] = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && T[i] > T[st.peek()]) {
                int top = st.pop();
                res[top] = i - top;
            }
            st.push(i);
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)（每元素入栈出栈各一次），空间 O(n)。

[!tip] 套路

  • "下一个更大"问题万能模板：单调栈存下标，弹栈时由"被弹者"和"触发者"算答案。[[#503. 下一个更大元素 II]] 同模板。

84. 柱状图中最大的矩形

柱状图里能画出的最大矩形面积。

思路脉络：固定每根柱子作"高"，矩形最大宽 = 左边第一个更矮的位置到右边第一个更矮的位置之间。所以对每根柱子找"左右第一个更矮"——正是单调栈（递增栈）。

[!example] 单调栈弹栈结算（动图）
加左右哨兵 0，递增栈存下标，遇更矮柱子弹栈结算：高=弹出柱，宽=当前 i − 新栈顶 − 1。本例最大矩形面积 10（高 5 × 宽 2）。

0084-largest-rect

加左右两个 0 哨兵柱简化边界：左哨兵让栈不空，右哨兵确保最后所有柱子被弹出结算。

graph LR A["遍历 i, h"] --> B{"栈非空且 h < 栈顶高?"} B -- 是 --> C["弹 top 作高"] C --> D["宽 = i - 新栈顶 - 1"] D --> E["算面积更新答案"] E --> B B -- 否 --> F["i 入栈"] F --> A 
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length, ans = 0;
        int[] h = new int[n + 2];                    // 左右加 0 哨兵
        System.arraycopy(heights, 0, h, 1, n);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < h.length; i++) {
            while (!st.isEmpty() && h[i] < h[st.peek()]) {
                int height = h[st.pop()];
                int width = i - st.peek() - 1;       // 新栈顶是左边界
                ans = Math.max(ans, height * width);
            }
            st.push(i);
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

  • 宽度计算 i - st.peek() - 1：弹栈后，新栈顶是"左边第一个更矮"的位置，右边界是当前 i（第一个让当前更矮的位置），宽 = 两者间距减一。哨兵 0 保证首元素和尾元素都能被结算。

[!tip] 关联

  • 这是单调栈的巅峰题。和 [[#42. 接雨水]] 看似都在柱状图上，思路相反：接雨水求"凹槽"（用递减栈算水量），最大矩形求"凸起"（用递增栈算面积）。[[#85. 最大矩形]] 把它扩展到二维矩阵。

13. 堆

堆用于维护"半个有序集"：快速取最大/最小。Java 用 PriorityQueue，默认小顶堆，Collections.reverseOrder() 变大顶堆。

两类核心场景：

  • Top-K：维护大小为 K 的堆，比堆顶差就丢弃，堆顶就是第 K 大/小。
  • 动态中位数：大顶堆装左半（较小的一半）、小顶堆装右半（较大的一半），两堆规模平衡。

215. 数组中的第 K 个最大元素

找第 K 大，要求 O(n) 期望。

思路脉络：三种。

小顶堆 O(n log K)：维护大小 K 的小顶堆，遍历完堆顶就是第 K 大。空间 O(K)。

大顶堆 O(n + K log n)：全部入大顶堆，弹 K 次。

快速选择 O(n) 期望：本题正解。基于快排的 partition：每次选 pivot 划分，看 pivot 位置和 K 的关系，只递归一侧。期望 O(n)，最坏 O(n²)（随机化 pivot 几乎不会退化）。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;                  // 第 K 大 = 升序第 (n-k) 个
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int p = partition(nums, l, r);
            if (p == k) return nums[p];
            else if (p < k) l = p + 1;
            else r = p - 1;
        }
        return nums[l];
    }
    int partition(int[] a, int l, int r) {
        int pivot = a[r], i = l;
        for (int j = l; j < r; j++) if (a[j] <= pivot) swap(a, i++, j);
        swap(a, i, r);
        return i;
    }
    void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

[!info] 复杂度
时间 O(n) 期望，空间 O(1)。

[!tip] 辨析

  • "第 K 大"转成"升序第 (n−K) 个"是关键转换，让快选的索引语义清晰。面试求 O(n) 必用快选，求简单可用小顶堆。

347. 前 K 个高频元素

返回出现频率前 K 高的元素。

思路脉络：先统计频率（哈希），再取前 K。取前 K 用小顶堆：堆大小 K，按频率建堆，频率比堆顶高才入。最后堆里就是前 K 高。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : nums) freq.merge(n, 1, Integer::sum);
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> freq.get(a) - freq.get(b)); // 小顶堆按频率
        for (int key : freq.keySet()) {
            pq.offer(key);
            if (pq.size() > k) pq.poll();            // 超过 K 弹最小的
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) res[i] = pq.poll();
        return res;
    }
}

[!info] 复杂度
时间 O(n log K)，空间 O(n)。

[!tip] 套路

  • "Top-K 频率"标准两步：哈希计数 + 小顶堆截断。堆大小恒为 K 是精髓——超出就弹最小，最终堆里是前 K 大。桶排序能做 O(n)，但堆更通用。

295. 数据流的中位数

数据流动态加入数字，随时能取中位数。addNum/findMedian 平均 O(log n)。

思路脉络：单有序结构取中位数 O(1) 但插入 O(n)。用两个堆：大顶堆 lo 装较小的一半（堆顶是这半的最大）、小顶堆 hi 装较大的一半（堆顶是这半的最小）。平衡两堆规模差 ≤1，中位数由两堆顶决定。

加入逻辑：先入 lo，把 lo 最大推到 hi，再若 lo 比 hi 少则从 hi 回补一个。保证 lo.size >= hi.size。

graph LR A["加入 num"] --> B["先入大顶堆 lo"] B --> C["lo 最大 → 小顶堆 hi"] C --> D{"lo 比 hi 少?"} D -- 是 --> E["hi 最小 → lo"] D -- 否 --> F["平衡完成"] E --> F F --> G["中位数 = lo 顶 或 两顶平均"] 
class MedianFinder {
    PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder()); // 大顶堆
    PriorityQueue<Integer> hi = new PriorityQueue<>();                            // 小顶堆
    public void addNum(int num) {
        lo.offer(num);
        hi.offer(lo.poll());      // lo 最大给 hi
        if (lo.size() < hi.size()) lo.offer(hi.poll()); // 平衡: hi 回补 lo
    }
    public double findMedian() {
        return lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;
    }
}

[!info] 复杂度
addNum O(log n)，findMedian O(1)。

[!warning] 易错点

  • 平衡方向：保证 lo.size >= hi.size，奇数时中位数取 lo.peek。若反过来保证 hi 多，奇数取 hi.peek，要和 findMedian 一致。lo.poll() 给 hi 这步保证"小半的最大 ≤ 大半的最小"的不变量。

14. 贪心算法

贪心每步选"当前最优"，赌局部最优能拼出全局最优。关键是证明"换一种选法不会更好"，否则贪心可能错。不像 DP 有通用框架，贪心要靠对具体问题的洞察。

121. 买卖股票的最佳时机

一次买卖，求最大利润。

思路脉络：遍历时维护"到当前为止的最低价" minPrice，每天算"今天卖能赚多少" = price - minPrice，取最大。一次遍历，O(n)。

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE, ans = 0;
        for (int p : prices) {
            minPrice = Math.min(minPrice, p);
            ans = Math.max(ans, p - minPrice);
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 关联

  • 这题是"一次买卖"特例。[[#122. 买卖股票的最佳时机 II]]（无限次买卖）贪心更直接：只要今天比昨天高就累加差值。[[#309. 最佳买卖股票含冷冻期]]、[[#188. 买卖股票的最佳时机 IV]] 才需 DP。

55. 跳跃游戏

数组每格表示最大跳跃步数，判断能否跳到末尾。

思路脉络：维护"当前能到达的最远位置" maxReach。遍历时若 i > maxReach 说明走不到这里，返回 false；否则更新 maxReach = max(maxReach, i + nums[i])，能覆盖末尾即 true。

graph LR A["遍历 i"] --> B{"i > maxReach?"} B -- 是 --> C["走不到, false"] B -- 否 --> D["maxReach = max(maxReach, i+nums[i])"] D --> E{"maxReach ≥ 末尾?"} E -- 是 --> F["true"] E -- 否 --> A 
class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) return false;
            maxReach = Math.max(maxReach, i + nums[i]);
        }
        return true;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

  • 判断 i > maxReach 要在更新之前：先确认当前位置可达，才能从这里继续跳。漏判会误把不可达当可达。

45. 跳跃游戏 II

保证能到末尾，求最少跳跃次数。

思路脉络：BFS 思想的贪心。维护当前跳跃能覆盖的范围 [l, r]，下一步能到的最远是这范围内所有格子的 i+nums[i] 最大值。每跳一步，l = r+1、r = nextMax，步数加一，直到 r 覆盖末尾。

graph LR A["l=0,r=0,步数=0"] --> B["扫 l..r 算 nextMax"] B --> C["步数++, l=r+1, r=nextMax"] C --> D{"r ≥ 末尾?"} D -- 是 --> E["返回步数"] D -- 否 --> B 
class Solution {
    public int jump(int[] nums) {
        int steps = 0, l = 0, r = 0;
        while (r < nums.length - 1) {
            int nextMax = 0;
            for (int i = l; i <= r; i++) nextMax = Math.max(nextMax, i + nums[i]);
            l = r + 1;
            r = nextMax;
            steps++;
        }
        return steps;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 直觉

  • 把每一步能到的范围当成 BFS 的一层，步数就是层数。这视角让"最少跳几步"自然映射成"BFS 几层到终点"。

763. 划分字母区间

把字符串切成尽量多的段，使每段内每个字母只出现在该段。

思路脉络：每个字母最后一次出现的位置是该段必须延伸到的下限。遍历时维护"当前段的最远边界" end = max(end, last[c])，当 i == end 时说明当前段所有字母都已在段内，可切。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i; // 记录每个字母最后位置
        List<Integer> res = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) { res.add(i - start + 1); start = i + 1; } // 可切
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 套路

  • "区间合并/分割"用"最远边界"统一处理：[[#56. 合并区间]] 按 end 排序后取 max，本题按 last 取 max。核心都是"用一个边界变量吸收所有约束"。

15. 动态规划

DP 的核心三问，每题先想清楚再写代码：

  1. 状态定义：dp[i]（或 dp[i][j]）代表什么？定义错了全盘错。
  2. 转移方程：dp[i] 由哪些更小的子问题推出？
  3. 边界与遍历顺序：初始值填什么？按什么顺序填保证依赖已就绪？

[!tip] 空间优化
一维 DP 只依赖前几项 → 压成两三个变量。二维 DP 只依赖上一行 → 压成一维数组。先写对再优化。

70. 爬楼梯

每次 1 或 2 阶，爬到第 n 阶有几种方法。

思路脉络：到第 n 阶只能从 n−1 阶爬一步或 n−2 阶爬两步，所以 dp[n] = dp[n-1] + dp[n-2]——斐波那契。边界 dp[0]=1（不动算 1 种）、dp[1]=1。

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
        return b;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 套路

  • "几种方法"类计数 DP，转移是"方案数相加"。和"最优值"类 DP（转移取 max/min）区分。

118. 杨辉三角

生成前 n 行杨辉三角。

思路脉络：每行首尾是 1，中间 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。逐行生成。

class Solution {
    public List<List<Integer>> generate(int n) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) row.add(1);
                else row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
            }
            res.add(row);
        }
        return res;
    }
}

[!info] 复杂度
时间 O(n²)，空间 O(n²)。

198. 打家劫舍

偷一排房子，相邻不能同偷，求最大金额。

思路脉络：dp[i] = 前 i 间能偷的最大金额。偷第 i 间则不能偷 i−1：dp[i] = dp[i-2] + nums[i]；不偷则 dp[i] = dp[i-1]。取大者。

class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int n : nums) {
            int cur = Math.max(prev1, prev2 + n);
            prev2 = prev1; prev1 = cur;
        }
        return prev1;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 关联

  • [[#213. 打家劫舍 II]]（环状）：分两种情况偷不偷首，各跑一次线性版本取 max。[[#337. 打家劫舍 III]]（树形）：树形 DP，每个节点返回"偷/不偷"两个值。

279. 完全平方数

把 n 表示成最少几个完全平方数之和。

思路脉络：dp[i] = 和为 i 的最少平方数个数。转移：枚举某个平方数 j*j，dp[i] = min(dp[i], dp[i-j*j] + 1)。这本质是完全背包——每个平方数可无限用，求装满 i 的最少件数。

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j * j <= i; j++)
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        return dp[n];
    }
}

[!info] 复杂度
时间 O(n√n)，空间 O(n)。

[!tip] 套路

  • "用若干物品凑成目标和/容量"是背包问题。完全背包（物品无限）内层正序遍历容量，0-1 背包（每物一件）内层逆序。[[#322. 零钱兑换]] 同模板。

322. 零钱兑换

用若干面额硬币凑成 amount 的最少枚数。

思路脉络：完全背包。dp[i] = 凑成金额 i 的最少硬币数。dp[i] = min(dp[i], dp[i-coin] + 1)。初始化 dp[0]=0，其余 MAX_VALUE。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);  // 用不可达大值代替 MAX, 避免+1溢出
        dp[0] = 0;
        for (int i = 1; i <= amount; i++)
            for (int c : coins)
                if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

[!info] 复杂度
时间 O(amount × 种类数)，空间 O(amount)。

[!warning] 易错点

  • 初始化用 amount+1 而非 Integer.MAX_VALUE：因为 MAX+1 会溢出成负数。amount+1 是"硬币最多 amount 枚（全用 1 元）"的上界，超过即不可达。

139. 单词拆分

字符串能否拆成字典里的若干词。

思路脉络：dp[i] = 前 i 个字符能否拆分。转移：枚举 j，若 dp[j] 为真且 s[j..i) 在字典，则 dp[i] = true。这题 DP 而非贪心。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++)
            for (int j = 0; j < i; j++)
                if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; break; }
        return dp[s.length()];
    }
}

[!info] 复杂度
时间 O(n² × 子串哈希)，空间 O(n)。

[!warning] 易错点

  • 内层 break 找到一个就停，避免无谓循环。子串 substring(j, i) 是 [j, i) 左闭右开。

300. 最长递增子序列

找最长严格递增子序列长度。

思路脉络：两种。

DP O(n²)：dp[i] = 以 nums[i] 结尾的 LIS 长度。对所有 j < i 且 nums[j] < nums[i]，dp[i] = max(dp[i], dp[j]+1)。

二分 O(n log n)：维护 tails 数组，tails[k] = 长度为 k+1 的递增子序列的最小末尾。每来一个数，二分找第一个 ≥ 它的位置替换。tails 长度即 LIS。

graph LR A["遍历 num"] --> B["二分找 tails 中第一个 ≥ num 的位置 p"] B --> C["tails[p] = num"] C --> D["LIS 长度 = tails.length"] D --> A 
class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int l = 0, r = len;
            while (l < r) {                            // 找第一个 ≥ num
                int m = (l + r) / 2;
                if (tails[m] < num) l = m + 1; else r = m;
            }
            tails[l] = num;
            if (l == len) len++;
        }
        return len;
    }
}

[!info] 复杂度
时间 O(n log n)，空间 O(n)。

[!warning] 易错点

  • tails 存的不是真实子序列，而是"各长度最小末尾"。替换保证后续更容易接上更长的，是贪心+二分的精妙。求具体序列要回溯，不能直接读 tails。

152. 乘积最大子数组

找乘积最大的连续子数组，含负数。

思路脉络：[[#53. 最大子数组和]] 的和变积，但负数让"最大"和"最小"会翻转——一个负数乘"最小负积"反而变最大。所以同时维护 maxProd 和 minProd，遇负数两者交换。

class Solution {
    public int maxProduct(int[] nums) {
        int maxP = nums[0], minP = nums[0], ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];
            if (n < 0) { int t = maxP; maxP = minP; minP = t; } // 负数翻转
            maxP = Math.max(n, maxP * n);
            minP = Math.min(n, minP * n);
            ans = Math.max(ans, maxP);
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

  • 遇负数先交换 maxP/minP 再算，否则用旧的 maxP*负数 得到的是更小值，逻辑错。max(n, maxP*n) 处理"从头开始新子数组"的情况。

416. 分割等和子集

能否把数组分成两份，使两份和相等。

思路脉络：总和 sum 奇数则不行。偶数则问"能否挑若干元素凑成 sum/2"——0-1 背包。dp[i] = 能否凑出和 i。每来一个数，从大到小更新（0-1 背包逆序，保证每个用一次）。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % 2 != 0) return false;
        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int n : nums)
            for (int i = target; i >= n; i--)     // 逆序, 0-1 背包
                dp[i] = dp[i] || dp[i - n];
        return dp[target];
    }
}

[!info] 复杂度
时间 O(n × target)，空间 O(target)。

[!warning] 易错点

  • 0-1 背包内层逆序：若正序，一个数会被用多次（变成完全背包）。逆序保证 dp[i-n] 还是上一轮的值，每物只用一次。

32. 最长有效括号

最长合法括号子串长度。

思路脉络：DP。dp[i] = 以 i 结尾的最长有效长度。s[i]==')' 时：

  • s[i-1]=='('：配对，dp[i] = dp[i-2] + 2。
  • s[i-1]==')' 且 s[i - dp[i-1] - 1]=='('：与前面一个 ) 对应的 ( 配对，dp[i] = dp[i-1] + dp[i - dp[i-1] - 2] + 2。
class Solution {
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int ans = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (dp[i - 1] > 0) {
                    int j = i - dp[i - 1] - 1;             // 跨过内部有效段找配对 (
                    if (j >= 0 && s.charAt(j) == '(') {
                        dp[i] = dp[i - 1] + 2 + (j >= 2 ? dp[j - 1] : 0);
                    }
                }
                ans = Math.max(ans, dp[i]);
            }
        }
        return ans;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(n)。

[!warning] 易错点

  • 第二种情况要"跨过 dp[i-1] 这段有效子串"找前面的 (，索引 i - dp[i-1] - 1。再加 dp[j-1] 把前面相连的有效段也并进来。栈法（存下标）更直观但 DP 法空间一致。

16. 多维动态规划

状态升到二维：dp[i][j] 通常表示"从起点到 (i,j)"或"两个序列的前缀"的解。难点在状态含义和遍历顺序——依赖关系跨行跨列，要确保填表时依赖项已就绪。

62. 不同路径

m×n 网格左上到右下，每次只往右或下，几种走法。

思路脉络：dp[i][j] = 到 (i,j) 的走法数。只能从左或上来，dp[i][j] = dp[i-1][j] + dp[i][j-1]。首行首列全 1。可压缩成一维。

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[j] += dp[j - 1];        // dp[j]=上, dp[j-1]=左
        return dp[n - 1];
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(n)。

[!tip] 套路

  • 网格 DP 一律"从左上来"。压缩成一维时，dp[j] 在更新前是"上一行同列"（上），dp[j-1] 是"本行左列"（左），正好凑齐。

64. 最小路径和

网格每格有代价，左上到右下路径最小代价和。

思路脉络：和 [[#62. 不同路径]] 同框架，把"方案数相加"换成"代价取 min"。dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。原地修改 grid 可省空间。

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;
                else if (i == 0) grid[i][j] += grid[i][j - 1];
                else if (j == 0) grid[i][j] += grid[i - 1][j];
                else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        return grid[m - 1][n - 1];
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(1)（原地）。

5. 最长回文子串

找最长回文子串。

思路脉络：中心扩展法最直观。回文以中心对称，中心可以是单字符（奇数长）或两字符间隙（偶数长）。对每个中心向两侧扩展，记录最长。

DP 法：dp[i][j] 表示 s[i..j] 是否回文，dp[i][j] = s[i]==s[j] && dp[i+1][j-1]。O(n²) 但常数大、空间 O(n²)，不如中心扩展。

graph LR A["每个中心 i"] --> B["奇数: 从 i 向两侧扩"] A --> C["偶数: 从 i,i+1 向两侧扩"] B --> D["记录最长起止"] C --> D D --> E["返回最长子串"] 
class Solution {
    public String longestPalindrome(String s) {
        int st = 0, max = 1;
        for (int i = 0; i < s.length(); i++) {
            int l1 = expand(s, i, i), l2 = expand(s, i, i + 1);
            int len = Math.max(l1, l2);
            if (len > max) { max = len; st = i - (len - 1) / 2; }
        }
        return s.substring(st, st + max);
    }
    int expand(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
        return r - l - 1;                  // 扩过头了, 回退一步的真实长度
    }
}

[!info] 复杂度
时间 O(n²)，空间 O(1)。

[!warning] 易错点

  • expand 返回 r - l - 1：循环退出时 l、r 已是不匹配的位置，真实回文是 (l+1, r-1)，长度 r-1 - (l+1) + 1 = r - l - 1。起点 i - (len-1)/2 对奇偶都成立。

1143. 最长公共子序列

两字符串的最长公共子序列长度。

思路脉络：dp[i][j] = s1[0..i] 与 s2[0..j] 的 LCS。字符相同则 dp[i][j] = dp[i-1][j-1] + 1；不同则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

graph LR A["dp[i][j]"] --> B{"s1[i]==s2[j]?"} B -- 是 --> C["dp[i-1][j-1] + 1"] B -- 否 --> D["max(dp[i-1][j], dp[i][j-1])"] 
class Solution {
    public int longestCommonSubsequence(String t1, String t2) {
        int m = t1.length(), n = t2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                if (t1.charAt(i - 1) == t2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        return dp[m][n];
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(mn)，可压缩到 O(min(m,n))。

[!tip] 套路

  • "两序列"DP 通用模板：相同加 1、不同取两边 max。[[#72. 编辑距离]]、[[#583. 两个字符串的删除操作]] 都在这框架上加权。下标用 i-1、j-1 对应字符，留出 dp[0][*]=0 边界。

72. 编辑距离

把 word1 变成 word2 的最少操作（增/删/改）次数。

思路脉络：[[#1143. 最长公共子序列]] 的进阶。dp[i][j] = w1[0..i] 变成 w2[0..j] 的最少操作。

  • 字符相同：dp[i][j] = dp[i-1][j-1]（不用操作）。
  • 不同：取三选一取 min：
    • dp[i-1][j] + 1：删 w1[i]。
    • dp[i][j-1] + 1：增一个 w2[j]。
    • dp[i-1][j-1] + 1：把 w1[i] 改成 w2[j]。

边界：dp[i][0] = i（全删）、dp[0][j] = j（全增）。

[!example] 二维 DP 表逐格填充（动图）
ab→abc：先填边界(全删/全增)，再逐格推。字符相同取左上 dp[i-1][j-1]；不同取左/上/左上三者 min+1。dp[2][3]=1：末尾增一个 c 即可。

0072-edit-distance

graph LR A["dp[i][j]"] --> B{"w1[i-1]==w2[j-1]?"} B -- 是 --> C["dp[i-1][j-1]"] B -- 否 --> D["删 dp[i-1][j]+1"] B -- 否 --> E["增 dp[i][j-1]+1"] B -- 否 --> F["改 dp[i-1][j-1]+1"] D --> G["三者取 min"] E --> G F --> G 
class Solution {
    public int minDistance(String w1, String w2) {
        int m = w1.length(), n = w2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                if (w1.charAt(i - 1) == w2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
            }
        return dp[m][n];
    }
}

[!info] 复杂度
时间 O(mn)，空间 O(mn)，可压缩到 O(n)（需保留上一行和左上角）。

[!warning] 易错点

  • 压缩成一维时，dp[i-1][j-1]（左上角）会被 dp[j-1] 的更新覆盖，要用 prev 变量暂存上一轮的 dp[j-1]。这是二维 DP 压缩的经典坑。

[!tip] 关联

  • 编辑距离是"两序列 DP"的集大成者，三种操作对应三个方向。理解了它，[[#583. 两个字符串的删除操作]]（只删不改）、[[#712. 两个字符串的最小 ASCII 删除和]]（带权删）都是降维版本。

17. 技巧

这类题靠特定 trick：位运算、摩尔投票、下标原地哈希、下一个排列的"魔法步骤"。trick 背后都有数学或不变量支撑，记住推导而非死记步骤。

136. 只出现一次的数字

数组里除一个数外每个出现两次，找那个出现一次的。O(n) 时间 O(1) 空间。

思路脉络：异或 ^ 的性质：a ^ a = 0、a ^ 0 = a、交换结合。把所有数异或起来，成对的抵消成 0，剩下就是那个只出现一次的。

class Solution {
    public int singleNumber(int[] nums) {
        int x = 0;
        for (int n : nums) x ^= n;
        return x;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!tip] 套路

  • 异或处理"成对抵消"。[[#137. 只出现一次的数字 II]]（其他出现三次）用位统计：每位对 3 取模。位运算是这类题的统一工具。

169. 多数元素

找出现超过 ⌊n/2⌋ 次的元素，保证存在。O(n) 时间 O(1) 空间。

思路脉络：摩尔投票。想象两军对战，同阵营人数 +1、异阵营人数 −1，人数归零就换候选。多数派超过半数，最终剩下的候选一定是它。正确性来自"多数派抵消掉所有少数派后还有盈余"。

graph LR A["遍历 n"] --> B{"n == 候选?"} B -- 是 --> C["count++"] B -- 否 --> D["count--"] D --> E{"count==0?"} E -- 是 --> F["换候选 = n, count=1"] E -- 否 --> A C --> A F --> A 
class Solution {
    public int majorityElement(int[] nums) {
        int cand = 0, cnt = 0;
        for (int n : nums) {
            if (cnt == 0) { cand = n; cnt = 1; }
            else if (n == cand) cnt++;
            else cnt--;
        }
        return cand;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

  • 摩尔投票只在"保证有多数元素（超过 n/2）"时直接返回候选。不保证时需二次遍历验证计数。本题保证存在，免验证。

75. 颜色分类

数组只有 0/1/2，原地把它们排成升序，不能排序库。

思路脉络：荷兰国旗问题，三指针一遍扫描。l 指向 0 的右边界、r 指向 2 的左边界、i 扫描。遇 0 换到 l、遇 2 换到 r、遇 1 跳过。换 2 后 i 不动（因为换回来的还没看）。

[!example] 荷兰国旗三指针（动图）
三区随扫描成型：[0,l) 全 0、[l,i) 全 1、(r,n) 全 2。遇 2 换到 r 后 i 不动是关键——换回的值还没判断；遇 0 换到 l 后 i++ 安全。

0075-sort-colors

graph LR A["i 扫描"] --> B{"nums[i]?"} B -- 0 --> C["与 l 交换, l++, i++"] B -- 1 --> D["i++"] B -- 2 --> E["与 r 交换, r--"] E --> F["i 不动, 看换回来的"] F --> B 
class Solution {
    public void sortColors(int[] nums) {
        int l = 0, r = nums.length - 1, i = 0;
        while (i <= r) {
            if (nums[i] == 0) { swap(nums, i++, l++); }
            else if (nums[i] == 2) { swap(nums, i, r--); } // i 不动
            else i++;
        }
    }
    void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

  • 换 2 后 i 不自增：从 r 换回来的可能是 0/1/2 任意值，得重新判断。换 0 后 i++ 安全，因为换到 i 的是 l 位置（l <= i，那里已是 1 或就是 i 自己）。

31. 下一个排列

把数组重排成字典序的下一个排列，没有更大排列就升序。

思路脉络：四步法，每步都有依据：

  1. 从右找第一个"降序对" i（nums[i] < nums[i+1]）——这是能变大的最低位。
  2. 从右找第一个比 nums[i] 大的 j——这是比原数大的最小替换。
  3. 交换 i、j。
  4. 反转 i+1 到末尾——降序变升序，让后缀最小。
graph LR A["从右找降序对 i"] --> B{"找到?"} B -- 否 --> C["整体反转(最小排列)"] B -- 是 --> D["从右找 >nums[i] 的 j"] D --> E["交换 i,j"] E --> F["反转 i+1..末尾"] 
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length, i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;      // 找降序对
        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) j--;                 // 找比 nums[i] 大的
            swap(nums, i, j);
        }
        reverse(nums, i + 1, n - 1);                        // 反转后缀
    }
    void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
    void reverse(int[] a, int l, int r) { while (l < r) swap(a, l++, r--); }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

  • 找 i 用 >=（要严格降序对的左端，跳过相等的）；找 j 用 <=（要严格大于 nums[i]）。两个比较符号方向别搞反。

287. 寻找重复数

n+1 个数取值 1..n，有一个重复，找出来。不能改数组，O(1) 空间。

思路脉络：三种。

二分：对值域 1..n 二分，统计 ≤mid 的个数，超过 mid 个说明重复在左半。

原地哈希：把 i 放到 nums[i]，冲突即重复。但会改数组，违规。

快慢指针（推荐）：把数组看成"i → nums[i]"的链表，重复数意味着有环。复用 [[#142. 环形链表 II]] 的找环入口算法，环入口就是重复数。

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0], fast = nums[nums[0]];
        while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; } // 相遇
        slow = 0;
        while (slow != fast) { slow = nums[slow]; fast = nums[fast]; }      // 入口
        return slow;
    }
}

[!info] 复杂度
时间 O(n)，空间 O(1)。

[!warning] 易错点

  • 快慢指针能用的前提是"值域 1..n 且索引 0..n"——nums[i] 永远是合法索引，构成链表。若有 0 值就崩。快指针起步 nums[nums[0]] 而非 nums[0]，让快慢真正不同步。

[!tip] 关联

  • 这是把"链表找环"迁移到"数组下标链"的妙用，和 [[#142. 环形链表 II]]、[[#202. 快乐数]] 同源：只要能定义"i → f(i)"的映射且存在环，快慢指针就能找入口。

写在最后

100 题刷完不是终点。建议二刷时关注三件事：

  1. 横向归类：把同套路的题放一起刷（如所有单调栈、所有两序列 DP），体会模板的复用。
  2. 纵向追问：每题问"还有别的解法吗""数据范围变大怎么办"，逼自己想优化。
  3. 手写默码：挑高频题（两数之和、反转链表、LRU、全排列、二分模板）闭着眼能写出无 bug 代码，面试就稳了。