Hot100

我发现，hot100 我刷了很多遍，但每次临近面试的时候，还是得从头刷一遍，这样效率太低了，该笔记的作用就是总结 hot100 的思路，以及给出比较优异的代码，之后复习，直接过思路 + 看代码即可，旨在提高算法复习效率。

每一道题包含思路 + python 和 Java 的代码实现，复习时只需要快速的过一遍思路即可。

LeetCode 01. 两数之和

难度：⭐ 简单  |  标签：数组 哈希表

🔗 LeetCode 原题链接

---

核心思路

利用哈希表存储已遍历的元素，在遍历过程中检查 target - nums[i] 是否已在哈希表中。

唯一需要注意的是：哈希表中存储的是当前遍历位置之前的所有数，因此不会重复使用同一个元素。

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, num in enumerate(nums):
            x = target - num
            if x in dic:
                return [dic[x], i]
            dic[num] = i
        return []

复杂度分析

• 时间复杂度：O(n) — 只需遍历数组一次
• 空间复杂度：O(n) — 哈希表最多存储 n 个元素

LeetCode 49. 字母异位词分组

难度：⭐⭐ 中等  |  标签：数组 哈希表 字符串 排序

🔗 LeetCode 原题链接

---

核心思路

对每个字符串按字典序排序，排序后相同的字符串即为字母异位词，放入同一组中。

• 排序后的字符串作为哈希表的 key
• 原始字符串加入对应 key 的列表中

PythonJava

from typing import List
from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = defaultdict(list)
        for s in strs:
            sorted_s = "".join(sorted(s))
            dic[sorted_s].append(s)
        return list(dic.values())

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

复杂度分析

• 时间复杂度：O(n × k log k) — n 为字符串个数，k 为字符串最大长度，每次排序 O(k log k)
• 空间复杂度：O(n × k) — 哈希表存储所有字符串

LeetCode 128. 最长连续序列

难度：⭐⭐ 中等  |  标签：数组 哈希表 并查集

🔗 LeetCode 原题链接

---

核心思路

为了实现 O(n) 时间复杂度，先将所有数放入哈希集合中，然后遍历集合：

• 若 x - 1 存在于集合中，则跳过（以 x-1 为起点的序列已经被统计过了）
• 若 x - 1 不存在，则 x 是一个序列起点，从它开始向后查找 x + 1, x + 2, ...

每轮更新最长序列长度即可。

PythonJava

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        n = len(nums)
        if not n:
            return 0

        s = set(nums)
        res = 1
        for x in s:
            if x - 1 in s:
                continue
            k, cur = 1, x + 1
            while cur in s:
                cur += 1
                k += 1
            res = max(res, k)

        return res

class Solution {
    public int longestConsecutive(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;

        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        int res = 1;
        for (int x : set) {
            if (set.contains(x - 1)) {
                continue;
            }
            int cur = x + 1;
            int k = 1;
            while (set.contains(cur)) {
                cur++;
                k++;
            }
            res = Math.max(res, k);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个元素最多被访问两次（一次加入集合，一次作为序列成员被检查）
• 空间复杂度：O(n) — 哈希集合存储所有元素

LeetCode 283. 移动零

难度：⭐ 简单  |  标签：数组 双指针

🔗 LeetCode 原题链接

---

核心思路

维护一个非零区间，遍历数组，将遇到的非零元素交换到非零区间的末尾，同时扩大非零区间。

这样遍历结束后，所有零元素自然被"挤"到了数组末尾，且保持了非零元素的相对顺序。

PythonJava

from typing import List

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """Do not return anything, modify nums in-place instead."""
        n = len(nums)
        j = 0  # 非零区的右边界（待插入位置）
        for i in range(n):
            if nums[i] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                j += 1

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        int j = 0; // 非零区的右边界（待插入位置）
        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
                j++;
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(n) — 一次遍历
• 空间复杂度：O(1) — 原地交换，只使用了常数额外空间

LeetCode 11. 盛最多水的容器

难度：⭐⭐ 中等  |  标签：数组 双指针 贪心

🔗 LeetCode 原题链接

---

核心思路

双指针 + 贪心，每次移动较矮的那一端：

• 初始时左右指针分别在 0 和 n-1，此时宽度最大
• 每次容器的盛水量由较矮的柱子决定：min(height[l], height[r]) * (r - l)
• 无论移动哪一端，宽度都在减小，所以要追求更高的高度
• 移动较矮的柱子，因为较矮的柱子不可能出现在更优解中（宽度变小，高度不变或更低，水量必定减少）

每一步只移动一端，O(n) 即可找到全局最优解。

PythonJava

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        l, r = 0, n - 1
        res = 0
        while l < r:
            res = max(res, min(height[l], height[r]) * (r - l))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return res

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int l = 0, r = n - 1;
        int res = 0;
        while (l < r) {
            res = Math.max(res, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 左右指针各向中间移动，总共遍历一次
• 空间复杂度：O(1) — 只使用了常数额外空间

LeetCode 15. 三数之和

难度：⭐⭐ 中等  |  标签：数组 双指针 排序

🔗 LeetCode 原题链接

---

核心思路

排序 + 双指针，将三层循环优化为两层：

1. 先对数组排序，方便去重和双指针移动
2. 固定 nums[i]，问题转化为在 [i+1, n-1] 中找两数之和等于 -nums[i]
3. 内层用双指针 j、k 从两端向中间逼近：
   • sum < 0 → j++（和太小，左指针右移）
   • sum > 0 → k--（和太大，右指针左移）
   • sum == 0 → 记录结果，然后跳过重复元素

去重要点

三处去重，缺一不可：

• 外层循环：i > 0 且 nums[i] == nums[i-1] 时跳过
• 找到解后：跳过与 nums[j] 相等的右邻元素
• 找到解后：跳过与 nums[k] 相等的左邻元素

PythonJava

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        res, n = [], len(nums)
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            j, k = i + 1, n - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s < 0:
                    j += 1
                elif s > 0:
                    k -= 1
                else:
                    res.append([nums[i], nums[j], nums[k]])
                    while j < k and nums[j] == nums[j + 1]:
                        j += 1
                    while j < k and nums[k] == nums[k - 1]:
                        k -= 1
                    j += 1
                    k -= 1
        return res

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1, k = n - 1;
            while (j < k) {
                int s = nums[i] + nums[j] + nums[k];
                if (s < 0) {
                    j++;
                } else if (s > 0) {
                    k--;
                } else {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while (j < k && nums[j] == nums[j + 1]) j++;
                    while (j < k && nums[k] == nums[k - 1]) k--;
                    j++;
                    k--;
                }
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n²) — 排序 O(n log n) + 双指针 O(n²)
• 空间复杂度：O(1) — 忽略排序栈开销，仅使用常数额外空间

LeetCode 42. 接雨水

难度：⭐⭐⭐ 困难  |  标签：数组 双指针 动态规划 单调栈

🔗 LeetCode 原题链接

---

核心思路

每个位置能接多少雨水，由左边最高柱子和右边最高柱子中较矮的那个决定：

\[ water[i] = \max\big(0,\ \min(lmax[i],\ rmax[i]) - height[i]\big) \]

其中 lmax[i] 表示 [0, i-1] 区间的最高柱子，rmax[i] 表示 [i+1, n-1] 区间的最高柱子。

• 从左到右遍历，计算每个位置的 lmax（左边最高）
• 从右到左遍历，计算每个位置的 rmax（右边最高）
• 最后遍历一遍，累加每个位置的接水量

PythonJava

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        lmax, rmax = [0] * n, [0] * n

        for i in range(1, n):
            lmax[i] = max(lmax[i - 1], height[i - 1])

        for i in range(n - 2, -1, -1):
            rmax[i] = max(rmax[i + 1], height[i + 1])

        res = 0
        for i in range(n):
            res += max(0, min(lmax[i], rmax[i]) - height[i])

        return res

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] lmax = new int[n];
        int[] rmax = new int[n];

        for (int i = 1; i < n; i++) {
            lmax[i] = Math.max(lmax[i - 1], height[i - 1]);
        }
        for (int i = n - 2; i >= 0; i--) {
            rmax[i] = Math.max(rmax[i + 1], height[i + 1]);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res += Math.max(0, Math.min(lmax[i], rmax[i]) - height[i]);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 三次线性遍历
• 空间复杂度：O(n) — 两个辅助数组存储左右最大值

LeetCode 03. 无重复字符的最长子串

难度：⭐⭐ 中等  |  标签：哈希表 字符串 滑动窗口

🔗 LeetCode 原题链接

---

核心思路

滑动窗口（双指针），维护一个无重复字符的窗口：

• 右指针 i 不断向右扩展，将新字符加入窗口计数
• 如果当前字符出现次数 > 1（即重复了），则左指针 j 不断右移，从窗口中移出字符，直到重复消除
• 每次迭代更新窗口最大长度 res = max(res, i - j + 1)

为什么左指针只能向右移动？

因为窗口右侧已经出现了重复字符，向左扩大只会包含更多重复字符，不可能得到更优解。

PythonJava

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0

        dic = defaultdict(int)  # 记录窗口中各字符出现次数
        n = len(s)
        res, j = 1, 0
        for i in range(n):
            dic[s[i]] += 1
            while dic[s[i]] > 1:       # 出现重复，收缩左边界
                dic[s[j]] -= 1
                j += 1
            res = max(res, i - j + 1)
        return res

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) return 0;

        Map<Character, Integer> map = new HashMap<>();
        int n = s.length();
        int res = 1, j = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
            while (map.get(c) > 1) {          // 出现重复，收缩左边界
                char left = s.charAt(j);
                map.put(left, map.get(left) - 1);
                j++;
            }
            res = Math.max(res, i - j + 1);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 左右指针各遍历一次
• 空间复杂度：O(Σ) — Σ 为字符集大小，通常为 128（ASCII）或 26（小写字母）

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

难度：⭐⭐ 中等  |  标签：哈希表 字符串 滑动窗口

🔗 LeetCode 原题链接

---

核心思路

固定窗口大小的滑动窗口 + 数组模拟哈希表（仅小写字母，数组最优）：

1. 用 need[26] 统计 p 中每个字符的出现次数
2. 用 cur[26] 统计当前窗口中每个字符的出现次数
3. 维护一个大小为 len(p) 的固定窗口，每次右移一步：
   • 当窗口大小 == len(p) 时，比较 cur == need
   • 若相等，则当前窗口左边界是一个异位词起点
   • 缩小窗口前，移出左边界的字符计数

PythonJava

from typing import List

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        need, cur = [0] * 26, [0] * 26
        n, m = len(s), len(p)
        res = []
        if n < m:
            return res

        for c in p:
            need[ord(c) - ord("a")] += 1

        l, r = 0, 0
        while r < n:
            cur[ord(s[r]) - ord("a")] += 1
            if r - l + 1 == m:
                if cur == need:
                    res.append(l)
                cur[ord(s[l]) - ord("a")] -= 1
                l += 1
            r += 1

        return res

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] need = new int[26];
        int[] cur = new int[26];
        int n = s.length(), m = p.length();
        List<Integer> res = new ArrayList<>();
        if (n < m) return res;

        for (char c : p.toCharArray()) {
            need[c - 'a']++;
        }

        int l = 0;
        for (int r = 0; r < n; r++) {
            cur[s.charAt(r) - 'a']++;
            if (r - l + 1 == m) {
                if (Arrays.equals(cur, need)) {
                    res.add(l);
                }
                cur[s.charAt(l) - 'a']--;
                l++;
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n × 26) ≈ O(n) — 每次窗口满时比较两个长度为 26 的数组，常数时间
• 空间复杂度：O(1) — 两个固定长度的辅助数组

LeetCode 560. 和为 K 的子数组

难度：⭐⭐ 中等  |  标签：数组 哈希表 前缀和

🔗 LeetCode 原题链接

---

核心思路

前缀和 + 哈希表统计，将连续子数组求和转化为前缀和之差：

\[ \text{sum}(l, r) = s[r] - s[l-1] = k \quad \Longrightarrow \quad s[l-1] = s[r] - k \]

• 遍历前缀和数组 s[i]，目标是找到前面有多少个 s[j] 满足 s[i] - s[j] == k
• 用哈希表记录每个前缀和出现的次数
• 初始化 dic[0] = 1（前缀和数组本身含 s[0] = 0）

PythonJava

from collections import defaultdict
from typing import List

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums = [0] + nums
        s = [0] * (n + 1)
        for i in range(1, n + 1):
            s[i] = s[i - 1] + nums[i]

        dic = defaultdict(int)
        dic[0] = 1
        res = 0
        for i in range(1, n + 1):
            target = s[i] - k
            res += dic[target]
            dic[s[i]] += 1

        return res

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + nums[i - 1];
        }

        Map<Integer, Integer> dic = new HashMap<>();
        dic.put(0, 1);
        int res = 0;
        for (int i = 1; i <= n; i++) {
            int target = s[i] - k;
            res += dic.getOrDefault(target, 0);
            dic.put(s[i], dic.getOrDefault(s[i], 0) + 1);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 一次遍历构建前缀和，一次遍历统计
• 空间复杂度：O(n) — 哈希表存储前缀和

LeetCode 239. 滑动窗口最大值

难度：⭐⭐⭐ 困难  |  标签：数组 队列 滑动窗口 单调队列

🔗 LeetCode 原题链接

---

核心思路

单调队列，维护一个双端队列，队列中存储的是元素的下标，且对应的值单调递减：

1. 清理过期：队头下标超出窗口范围（i - maxq[0] + 1 > k）时，弹出队头
2. 维护单调：从队尾开始，弹出所有值 ≤ 当前值的元素（它们不可能是之后窗口的最大值了）
3. 加入当前：当前元素下标入队
4. 记录答案：当 i >= k-1 时，队头就是当前窗口的最大值

PythonJava

from typing import List
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        maxq, res = deque(), []
        n = len(nums)
        for i in range(n):
            # 1. 删除过期的元素
            while maxq and i - maxq[0] + 1 > k:
                maxq.popleft()

            # 2. 删除没用的元素（比当前值小，不可能成为后续窗口的最大值）
            while maxq and nums[maxq[-1]] <= nums[i]:
                maxq.pop()

            # 3. 当前元素入队
            maxq.append(i)

            # 4. 记录窗口最大值
            if i >= k - 1:
                res.append(nums[maxq[0]])

        return res

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> maxq = new ArrayDeque<>();
        int n = nums.length;
        int[] res = new int[n - k + 1];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            // 1. 删除过期的元素
            while (!maxq.isEmpty() && i - maxq.peekFirst() + 1 > k) {
                maxq.pollFirst();
            }
            // 2. 删除没用的元素
            while (!maxq.isEmpty() && nums[maxq.peekLast()] <= nums[i]) {
                maxq.pollLast();
            }
            // 3. 当前元素入队
            maxq.offerLast(i);
            // 4. 记录窗口最大值
            if (i >= k - 1) {
                res[idx++] = nums[maxq.peekFirst()];
            }
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个元素最多入队一次、出队一次
• 空间复杂度：O(k) — 单调队列最多存储 k 个元素

LeetCode 76. 最小覆盖子串

难度：⭐⭐⭐ 困难  |  标签：哈希表 字符串 滑动窗口

🔗 LeetCode 原题链接

---

核心思路

滑动窗口 + cnt 计数优化：

1. 右指针不断向右扩展，直到窗口包含 t 中所有字符（找到一个合法解）
2. 然后左指针不断右移收缩窗口，寻找最短的合法解（最优解）
3. 用 cnt 记录当前窗口中已满足 t 中字符要求的字符个数，避免每次都去比较两个哈希表

cnt 如何更新？

• 右移 r 时：若 cur[s[r]] <= need[s[r]]，说明这个字符是"有用"的，cnt++
• 左移 l 时：若 cur[s[l]] < need[s[l]]（移出后不满足需求了），cnt--

PythonJava

from collections import defaultdict

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        n, m = len(s), len(t)
        if n < m:
            return ""

        minl, pos = float("inf"), 0
        need, cur = defaultdict(int), defaultdict(int)
        for c in t:
            need[c] += 1

        l, cnt = 0, 0
        for r in range(n):
            cur[s[r]] += 1
            if cur[s[r]] <= need[s[r]]:
                cnt += 1

            while cnt >= m:
                if r - l + 1 < minl:
                    minl = r - l + 1
                    pos = l
                if need[s[l]] > 0:
                    cur[s[l]] -= 1
                    if cur[s[l]] < need[s[l]]:
                        cnt -= 1
                l += 1

        return s[pos:pos + minl] if minl != float("inf") else ""

class Solution {
    public String minWindow(String s, String t) {
        int n = s.length(), m = t.length();
        if (n < m) return "";

        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> cur = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int minLen = Integer.MAX_VALUE, pos = 0;
        int l = 0, cnt = 0;

        for (int r = 0; r < n; r++) {
            char rc = s.charAt(r);
            cur.put(rc, cur.getOrDefault(rc, 0) + 1);
            if (cur.get(rc) <= need.getOrDefault(rc, 0)) {
                cnt++;
            }

            while (cnt >= m) {
                if (r - l + 1 < minLen) {
                    minLen = r - l + 1;
                    pos = l;
                }
                char lc = s.charAt(l);
                if (need.containsKey(lc)) {
                    cur.put(lc, cur.get(lc) - 1);
                    if (cur.get(lc) < need.get(lc)) {
                        cnt--;
                    }
                }
                l++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(pos, pos + minLen);
    }
}

复杂度分析

• 时间复杂度：O(n) — 左右指针各遍历一次
• 空间复杂度：O(Σ) — Σ 为字符集大小

LeetCode 53. 最大子数组和

难度：⭐⭐ 中等  |  标签：数组 分治 动态规划

🔗 LeetCode 原题链接

---

核心思路

经典 DP，定义 f[i] 为以 nums[i] 结尾的最大子数组和：

\[ f[i] = \max\big(f[i-1] + nums[i],\ nums[i]\big) \]

• 要么接在前面的子数组后面（f[i-1] + nums[i]）
• 要么自己新开一个子数组（nums[i]）

最终答案为所有 f[i] 中的最大值。

PythonJava

from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        f = [i for i in nums]
        res = f[0]
        for i in range(1, n):
            f[i] = max(f[i - 1] + nums[i], nums[i])
            res = max(res, f[i])
        return res

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        f[0] = nums[0];
        int res = f[0];
        for (int i = 1; i < n; i++) {
            f[i] = Math.max(f[i - 1] + nums[i], nums[i]);
            res = Math.max(res, f[i]);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 一次遍历
• 空间复杂度：O(n) — DP 数组，可优化为 O(1)（只用两个变量滚动）

LeetCode 56. 合并区间

难度：⭐⭐ 中等  |  标签：数组 排序

🔗 LeetCode 原题链接

---

核心思路

先按区间左端点排序，然后遍历合并：

• 当前区间左端点 > ed（与维护的区间不重叠）→ 将维护的区间加入答案，更新为当前区间
• 否则（重叠）→ 更新 ed = max(ed, 当前区间右端点)

最后别忘了把最后一个区间加入答案。

PythonJava

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        if n <= 1:
            return intervals

        intervals.sort(key=lambda x: x[0])

        st, ed = intervals[0][0], intervals[0][1]
        ans = []
        for i in range(1, n):
            if intervals[i][0] <= ed:
                ed = max(ed, intervals[i][1])
            else:
                ans.append([st, ed])
                st, ed = intervals[i][0], intervals[i][1]

        ans.append([st, ed])
        return ans

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        if (n <= 1) return intervals;

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> ans = new ArrayList<>();
        int st = intervals[0][0], ed = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] <= ed) {
                ed = Math.max(ed, intervals[i][1]);
            } else {
                ans.add(new int[]{st, ed});
                st = intervals[i][0];
                ed = intervals[i][1];
            }
        }
        ans.add(new int[]{st, ed});

        return ans.toArray(new int[ans.size()][]);
    }
}

复杂度分析

• 时间复杂度：O(n log n) — 排序主导
• 空间复杂度：O(log n) — 排序栈空间

LeetCode 189. 轮转数组

难度：⭐⭐ 中等  |  标签：数组 数学 双指针

🔗 LeetCode 原题链接

---

核心思路

将向右轮转 k 个位置，拆分为三次反转即可原地完成：

1. 整体反转：[0, n-1]
2. 反转前 k 个：[0, k-1]
3. 反转后 n-k 个：[k, n-1]

注意 k 先对 n 取模，避免多余轮转。

PythonJava

from typing import List

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """Do not return anything, modify nums in-place instead."""
        n = len(nums)
        k %= n

        def reverse(arr, st, ed):
            while st < ed:
                arr[st], arr[ed] = arr[ed], arr[st]
                st += 1
                ed -= 1

        reverse(nums, 0, n - 1)
        reverse(nums, 0, k - 1)
        reverse(nums, k, n - 1)

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    private void reverse(int[] arr, int st, int ed) {
        while (st < ed) {
            int tmp = arr[st];
            arr[st] = arr[ed];
            arr[ed] = tmp;
            st++;
            ed--;
        }
    }
}

复杂度分析

• 时间复杂度：O(n) — 三次反转，每次 O(n)
• 空间复杂度：O(1) — 原地反转

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

难度：⭐⭐ 中等  |  标签：数组 前缀和

🔗 LeetCode 原题链接

---

核心思路

不能用除法，且要求 O(1) 额外空间（输出数组不计入）。

两遍遍历：

1. 第一遍（从左到右）：用输出数组 res[i] 记录 nums[i] 左侧所有元素的乘积。
2. 第二遍（从右到左）：用一个变量维护右侧乘积，依次乘到 res[i] 上，得到最终结果。

这样每个位置的结果 = 左侧乘积 × 右侧乘积，无需额外数组。

PythonJava

from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n
        # 第一遍：res[i] 记录左侧乘积
        pre = nums[0]
        for i in range(1, n):
            res[i] = pre
            pre *= nums[i]
        # 第二遍：乘上右侧乘积
        pre = nums[n - 1]
        for i in range(n - 2, -1, -1):
            res[i] *= pre
            pre *= nums[i]
        return res

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, 1);
        // 第一遍：res[i] 记录左侧乘积
        int pre = nums[0];
        for (int i = 1; i < n; i++) {
            res[i] = pre;
            pre *= nums[i];
        }
        // 第二遍：乘上右侧乘积
        pre = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            res[i] *= pre;
            pre *= nums[i];
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 两次线性遍历
• 空间复杂度：O(1) — 仅输出数组占用空间（不计入额外空间）

LeetCode 41. 缺失的第一个正数

难度：⭐⭐⭐ 困难  |  标签：数组 哈希表

🔗 LeetCode 原题链接

---

核心思路

答案一定在 [1, n+1] 范围内，因此可以把原数组当作哈希表使用：

• 将每个在 [1, n] 范围内的数 x 放到下标 x - 1 的位置上
• 范围外的数忽略（它们不可能是答案）

交换完成后，再次遍历数组，第一个满足 nums[i] != i + 1 的位置，其 i + 1 就是缺失的最小正整数；如果全部对上，则答案为 n + 1。

注意

交换后换回来的新数也要继续映射，因此内层要用 while 而非 if。

PythonJava

from typing import List

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            # 把 nums[i] 放到它该去的位置（下标 nums[i] - 1）
            while 0 < nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                k = nums[i]
                nums[k - 1], nums[i] = nums[i], nums[k - 1]

        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        return n + 1

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            // 将 nums[i] 放到下标 nums[i] - 1（如果它在 [1, n] 范围内）
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                int k = nums[i];
                int tmp = nums[k - 1];
                nums[k - 1] = nums[i];
                nums[i] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个元素最多被交换一次
• 空间复杂度：O(1) — 原地交换，仅使用常数额外空间

LeetCode 73. 矩阵置零

难度：⭐⭐ 中等  |  标签：数组 矩阵

🔗 LeetCode 原题链接

---

核心思路

要求原地算法，O(1) 额外空间。用第 0 行和第 0 列作为标记位：

步骤

1. 用两个变量 row、col 分别记录第 0 行和第 0 列本身是否包含 0
2. 遍历整个矩阵，若 matrix[i][j] == 0，则将 matrix[0][j] 和 matrix[i][0] 置为 0（用第 0 行/列做标记）
3. 根据第 0 行和第 0 列的标记，将对应行/列置零（跳过第 0 行/列本身）
4. 最后根据 row、col 决定是否将第 0 行/列置零

PythonJava

from typing import List

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        n, m = len(matrix), len(matrix[0])
        row, col = 0, 0

        # 1. 记录第 0 行、第 0 列本身是否有 0
        for i in range(n):
            if matrix[i][0] == 0:
                col = 1
                break
        for j in range(m):
            if matrix[0][j] == 0:
                row = 1
                break

        # 2. 用第 0 行、第 0 列标记所有其他位置
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        # 3. 根据标记置零（跳过第 0 行/列）
        for i in range(1, n):
            if matrix[i][0] == 0:
                for j in range(m):
                    matrix[i][j] = 0
        for j in range(1, m):
            if matrix[0][j] == 0:
                for i in range(n):
                    matrix[i][j] = 0

        # 4. 处理第 0 行和第 0 列
        if row:
            for j in range(m):
                matrix[0][j] = 0
        if col:
            for i in range(n):
                matrix[i][0] = 0

class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        boolean row = false, col = false;

        // 1. 记录第 0 行、第 0 列本身是否有 0
        for (int i = 0; i < n; i++) {
            if (matrix[i][0] == 0) {
                col = true;
                break;
            }
        }
        for (int j = 0; j < m; j++) {
            if (matrix[0][j] == 0) {
                row = true;
                break;
            }
        }

        // 2. 用第 0 行、第 0 列标记所有其他位置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        // 3. 根据标记置零（跳过第 0 行/列）
        for (int i = 1; i < n; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 0; j < m; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 1; j < m; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 0; i < n; i++) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 4. 处理第 0 行和第 0 列
        if (row) {
            for (int j = 0; j < m; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col) {
            for (int i = 0; i < n; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(m × n) — 遍历矩阵两次
• 空间复杂度：O(1) — 仅用两个额外变量

LeetCode 54. 螺旋矩阵

难度：⭐⭐ 中等  |  标签：数组 矩阵 模拟

🔗 LeetCode 原题链接

---

核心思路

按 右 → 下 → 左 → 上 的顺序模拟遍历，遇到边界或已访问过的元素就切换方向。

方向数组 directions = [(0,1), (1,0), (0,-1), (-1,0)] 对应四个方向，每次越界/重复时 idx = (idx + 1) % 4 转向。

使用一个特殊标记（666）标记已访问位置，避免额外空间。

PythonJava

from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        n, m = len(matrix), len(matrix[0])
        res = []
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        i, j, idx = 0, 0, 0

        for _ in range(n * m):
            res.append(matrix[i][j])
            matrix[i][j] = 666  # 标记已访问

            nx, ny = i + directions[idx][0], j + directions[idx][1]
            if nx < 0 or nx >= n or ny < 0 or ny >= m or matrix[nx][ny] == 666:
                idx = (idx + 1) % 4
                nx, ny = i + directions[idx][0], j + directions[idx][1]

            i, j = nx, ny

        return res

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int i = 0, j = 0, idx = 0;

        for (int t = 0; t < n * m; t++) {
            res.add(matrix[i][j]);
            matrix[i][j] = 666;  // 标记已访问

            int nx = i + dirs[idx][0];
            int ny = j + dirs[idx][1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || matrix[nx][ny] == 666) {
                idx = (idx + 1) % 4;
                nx = i + dirs[idx][0];
                ny = j + dirs[idx][1];
            }
            i = nx;
            j = ny;
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(m × n) — 每个元素恰好访问一次
• 空间复杂度：O(1) — 不考虑输出数组，仅用常数额外空间

LeetCode 48. 旋转图像

难度：⭐⭐ 中等  |  标签：数组 矩阵 数学

🔗 LeetCode 原题链接

---

核心思路

顺时针旋转 90° = 转置 + 每行反转，两步均原地完成：

1. 转置矩阵：沿主对角线（左上到右下）对称交换 matrix[i][j] ↔ matrix[j][i]
2. 水平反转：逐行将左右元素对调

逆时针旋转 90° 则改为 转置 + 每列反转。

PythonJava

from typing import List

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)

        # 1. 转置
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        # 2. 水平反转
        for i in range(n):
            l, r = 0, n - 1
            while l < r:
                matrix[i][l], matrix[i][r] = matrix[i][r], matrix[i][l]
                l += 1
                r -= 1

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // 1. 转置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }

        // 2. 水平反转
        for (int i = 0; i < n; i++) {
            int l = 0, r = n - 1;
            while (l < r) {
                int tmp = matrix[i][l];
                matrix[i][l] = matrix[i][r];
                matrix[i][r] = tmp;
                l++;
                r--;
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(n²) — 两次遍历，每次 O(n²)
• 空间复杂度：O(1) — 原地交换

LeetCode 240. 搜索二维矩阵 II

难度：⭐⭐ 中等  |  标签：数组 二分查找 矩阵 分治

🔗 LeetCode 原题链接

---

核心思路

矩阵每行递增、每列也递增，利用有序性逐行二分：

• 遍历每一行，若 target 可能在该行内（即 ≤ 该行最大值 matrix[i][m-1]），则对该行做存在性二分查找（while l ≤ r）
• 找到直接返回 true，全部遍历完返回 false

另一种巧妙思路：Z 字形搜索

从右上角 (0, m-1) 出发：

• 若 当前值 > target → 向左移动（列减 1）
• 若 当前值 < target → 向下移动（行加 1）
• 相等则返回 true
  

时间复杂度 O(m + n)，空间 O(1)。

PythonJava

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n, m = len(matrix), len(matrix[0])
        for i in range(n):
            if target <= matrix[i][m - 1]:
                l, r = 0, m - 1
                while l <= r:
                    mid = (l + r) >> 1
                    if matrix[i][mid] < target:
                        l = mid + 1
                    elif matrix[i][mid] > target:
                        r = mid - 1
                    else:
                        return True
        return False

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length;
        for (int i = 0; i < n; i++) {
            if (target <= matrix[i][m - 1]) {
                int l = 0, r = m - 1;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (matrix[i][mid] < target) {
                        l = mid + 1;
                    } else if (matrix[i][mid] > target) {
                        r = mid - 1;
                    } else {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：O(n log m) — 最多对 n 行做二分，每行 O(log m)
• 空间复杂度：O(1) — 仅用常数额外空间

LeetCode 206. 反转链表

难度：⭐ 简单  |  标签：链表 递归

🔗 LeetCode 原题链接

---

核心思路

迭代反转，维护两个指针：

• pre 指向前一个结点（初始为 None/null）
• cur 指向当前结点，每次将 cur.next 指向 pre
• 移动前先保存 cur.next 到临时变量，防止断链

PythonJava

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, pre = head, None
        while cur:
            ne = cur.next   # 保存下一个结点
            cur.next = pre  # 反转指向
            pre = cur       # pre 前移
            cur = ne        # cur 前移
        return pre

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null;
        while (cur != null) {
            ListNode ne = cur.next;  // 保存下一个结点
            cur.next = pre;          // 反转指向
            pre = cur;               // pre 前移
            cur = ne;                // cur 前移
        }
        return pre;
    }
}

复杂度分析

• 时间复杂度：O(n) — 一次遍历
• 空间复杂度：O(1) — 仅用两个指针

LeetCode 160. 相交链表

难度：⭐ 简单  |  标签：链表 双指针

🔗 LeetCode 原题链接

---

核心思路

双指针各自从两个链表头出发，走到尽头后互换起点继续走：

• p1 从 headA 出发，走到 null 后切换到 headB
• p2 从 headB 出发，走到 null 后切换到 headA
• 如果有交点，两个指针会在交点相遇；如果无交点，则同时走到 null 返回空

这样 p1 和 p2 走过的路径长度相同，保证了同时到达交点。

PythonJava

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        p1, p2 = headA, headB
        while p1 != p2:
            p1 = p1.next if p1 else headB
            p2 = p2.next if p2 else headA
        return p1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            p1 = (p1 != null) ? p1.next : headB;
            p2 = (p2 != null) ? p2.next : headA;
        }
        return p1;
    }
}

复杂度分析

• 时间复杂度：O(m + n) — 最多遍历两个链表各一次
• 空间复杂度：O(1) — 仅用两个指针

LeetCode 234. 回文链表

难度：⭐ 简单  |  标签：链表 双指针 递归

🔗 LeetCode 原题链接

---

核心思路

要求 O(1) 空间，三步走：

1. 快慢指针找中点：fast 每次走两步，slow 每次走一步，fast 走到末尾时 slow 恰好在（左）中点
2. 反转右半部分：从 slow.next 开始反转，并将 slow.next 置空断开
3. 逐元素比较：左右两半同时遍历，值全部相等即为回文

快慢指针写法

中点条件为 while fast.next and fast.next.next，这样链表长度为奇数时左半会比右半多一个（中间结点不参与比较，值不重要）。

PythonJava

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return True

        # 1. 快慢指针找中点
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # 2. 反转后半部分
        temp = slow.next
        slow.next = None
        new_head = self.reverse(temp)

        # 3. 比较
        while head and new_head:
            if head.val != new_head.val:
                return False
            head = head.next
            new_head = new_head.next
        return True

    def reverse(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            ne = cur.next
            cur.next = pre
            pre = cur
            cur = ne
        return pre

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // 1. 快慢指针找中点
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 2. 反转后半部分
        ListNode temp = slow.next;
        slow.next = null;
        ListNode newHead = reverse(temp);

        // 3. 比较
        while (head != null && newHead != null) {
            if (head.val != newHead.val) return false;
            head = head.next;
            newHead = newHead.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode ne = cur.next;
            cur.next = pre;
            pre = cur;
            cur = ne;
        }
        return pre;
    }
}

复杂度分析

• 时间复杂度：O(n) — 找中点 O(n) + 反转 O(n/2) + 比较 O(n/2)
• 空间复杂度：O(1) — 仅用指针变量

LeetCode 141. 环形链表

难度：⭐ 简单  |  标签：链表 双指针

🔗 LeetCode 原题链接

---

核心思路

Floyd 判圈算法（快慢指针）：

• slow 每次走一步，fast 每次走两步
• 如果链表有环，fast 一定会追上 slow，二者相遇
• 如果 fast 走到 null，说明无环

PythonJava

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = 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;
    }
}

复杂度分析

• 时间复杂度：O(n) — 最坏情况下遍历链表一次
• 空间复杂度：O(1) — 仅用两个指针

LeetCode 142. 环形链表 II

难度：⭐⭐ 中等  |  标签：链表 双指针

🔗 LeetCode 原题链接

---

核心思路

在 [[141]] 快慢指针判环的基础上，找到环的入口：

1. 快慢指针相遇：slow 每次走 1 步，fast 每次走 2 步，直到相遇
2. 找环入口：将 head 指针重置到链表头，slow 留在相遇点，两者同步每次走 1 步，相遇点即为环入口

为什么这样能找到环入口？

设：

• \(a\) = 链表头到环入口的距离
• \(b\) = 环入口到相遇点的距离
• \(c\) = 相遇点到环入口的距离（即环剩余部分，环长 \(= b + c\)）

相遇时，slow 走了 \(a + b\)，fast 走了 \(a + b + k \cdot (b + c)\)。

因为 fast 路程是 slow 的 2 倍：

\[ a + b + k \cdot (b + c) = 2(a + b) \]

化简得：

\[ a = k \cdot (b + c) - b = (k-1)(b + c) + c \]

即 \(a \equiv c \pmod{环长}\)，所以 head 和 slow 同速移动，最终会在环入口相遇。

PythonJava

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                # 相遇后，head 和 slow 同步走，相遇即环入口
                while head != slow:
                    head = head.next
                    slow = slow.next
                return head
        return None

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
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) {
                while (head != slow) {
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
        }
        return null;
    }
}

复杂度分析

• 时间复杂度：O(n) — 快慢指针相遇 O(n) + 找入口 O(n)
• 空间复杂度：O(1) — 仅用指针变量

LeetCode 21. 合并两个有序链表

难度：⭐ 简单  |  标签：链表 双指针 归并

🔗 LeetCode 原题链接

---

核心思路

经典的二路归并，使用 dummy 哑结点简化边界处理：

• 同时遍历两个链表，取较小值接在结果链表尾部
• 其中一个链表遍历完后，直接将另一个链表的剩余部分接上（无需 while，直接 cur.next = p1/p2）

PythonJava

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        p1, p2 = list1, list2
        dummy = ListNode(-1)
        cur = dummy

        while p1 and p2:
            if p1.val < p2.val:
                cur.next = p1
                p1 = p1.next
            else:
                cur.next = p2
                p2 = p2.next
            cur = cur.next

        if p1:
            cur.next = p1
        if p2:
            cur.next = p2
        return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p1 = list1, p2 = list2;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                cur.next = p1;
                p1 = p1.next;
            } else {
                cur.next = p2;
                p2 = p2.next;
            }
            cur = cur.next;
        }

        if (p1 != null) cur.next = p1;
        if (p2 != null) cur.next = p2;

        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(m + n) — 遍历两个链表各一次
• 空间复杂度：O(1) — 仅用指针变量

LeetCode 2. 两数相加

难度：⭐⭐ 中等  |  标签：链表 数学 模拟

🔗 LeetCode 原题链接

---

核心思路

模拟高精度加法，链表头为最低位，从低位到高位逐位相加：

• 维护一个进位值 t，初始为 0
• 同时遍历两个链表，每次将对应位 + 进位相加
• t % 10 为当前位，t //= 10 为下一进位
• 最后若 t != 0，还需额外补一个结点

PythonJava

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        cur = dummy
        t = 0  # 进位

        while l1 or l2:
            if l1:
                t += l1.val
                l1 = l1.next
            if l2:
                t += l2.val
                l2 = l2.next

            cur.next = ListNode(t % 10)
            t //= 10
            cur = cur.next

        if t:
            cur.next = ListNode(1)

        return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int t = 0;  // 进位

        while (l1 != null || l2 != null) {
            if (l1 != null) {
                t += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                t += l2.val;
                l2 = l2.next;
            }
            cur.next = new ListNode(t % 10);
            t /= 10;
            cur = cur.next;
        }

        if (t != 0) {
            cur.next = new ListNode(1);
        }

        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(max(m, n)) — 遍历较长的链表
• 空间复杂度：O(1) — 不考虑输出链表

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

难度：⭐⭐ 中等  |  标签：链表 双指针

🔗 LeetCode 原题链接

---

核心思路

一趟扫描，用快慢指针找到倒数第 n + 1 个结点：

1. 快指针先走 n 步
2. 然后快慢指针一起走，直到快指针走到末尾
3. 此时慢指针指向倒数第 n + 1 个结点，执行 slow.next = slow.next.next 删除目标结点

使用 dummy 哑结点统一处理删除头结点的边界情况。

PythonJava

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(-1, head)
        slow, fast = dummy, dummy

        # 快指针先走 n 步
        for _ in range(n):
            fast = fast.next

        # 一起走到末尾
        while fast.next:
            fast = fast.next
            slow = slow.next

        # 删除倒数第 n 个
        slow.next = slow.next.next
        return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode slow = dummy, fast = dummy;

        // 快指针先走 n 步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // 一起走到末尾
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除倒数第 n 个
        slow.next = slow.next.next;
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(n) — 一趟扫描
• 空间复杂度：O(1) — 仅用指针变量

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

难度：⭐⭐ 中等  |  标签：链表 模拟

🔗 LeetCode 原题链接

---

核心思路

纯指针操作，画图即可理清：

• 用 dummy 哑结点统一处理
• 每次取 cur.next（p）和 cur.next.next（q）两两交换
• 先保存 q.next（ne），然后依次调整指针，最后 cur 移动到下一组的前驱位置

交换前：cur → p → q → ne
交换后：cur → q → p → ne

PythonJava

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-1, head)
        cur = dummy
        while cur.next and cur.next.next:
            p, q = cur.next, cur.next.next
            ne = q.next

            q.next = p
            p.next = ne
            cur.next = q
            cur = p

        return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            ListNode p = cur.next, q = cur.next.next;
            ListNode ne = q.next;

            q.next = p;
            p.next = ne;
            cur.next = q;
            cur = p;
        }
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(n) — 一次遍历
• 空间复杂度：O(1) — 仅用指针变量

LeetCode 25. K 个一组翻转链表

难度：⭐⭐⭐ 困难  |  标签：链表 模拟 递归

🔗 LeetCode 原题链接

---

核心思路

将链表按 k 个一组进行反转，每组反转后衔接回原链表：

1. 先统计总节点数 n
2. 每次取 k 个节点反转：
   • 保存 k 个节点之后的后续节点 ne
   • 反转当前 k 个节点，得到新头 newHead 和旧头 oldHead
   • 将反转后的子链表接回：cur → newHead → ... → oldHead → ne
   • cur 移动到 oldHead（当前组的尾部），准备处理下一组

原链表：... → cur → a₁ → a₂ → ... → aₖ → ne → ...
反转后：... → cur → aₖ → ... → a₂ → a₁ → ne → ...

PythonJava

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(-1, head)

        # 1. 统计节点个数
        n = 0
        temp = dummy.next
        while temp:
            temp = temp.next
            n += 1

        # 2. k 个一组去反转
        cur = dummy
        while n >= k:
            # 保存这 k 个节点的下一个节点
            ne = cur
            for _ in range(k + 1):
                ne = ne.next

            new_head, old_head = self.reverse_k(cur.next, k)

            # 接回原链表
            cur.next = new_head
            old_head.next = ne
            cur = old_head

            n -= k

        return dummy.next

    def reverse_k(self, head: Optional[ListNode], k: int):
        """反转前 k 个节点，返回 (新头, 旧头)"""
        old_head = head
        pre, cur = None, head
        while k:
            ne = cur.next
            cur.next = pre
            pre = cur
            cur = ne
            k -= 1
        return pre, old_head

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1, head);

        // 1. 统计节点个数
        int n = 0;
        ListNode temp = dummy.next;
        while (temp != null) {
            temp = temp.next;
            n++;
        }

        // 2. k 个一组去反转
        ListNode cur = dummy;
        while (n >= k) {
            // 保存这 k 个节点的下一个节点
            ListNode ne = cur;
            for (int i = 0; i < k + 1; i++) {
                ne = ne.next;
            }

            ListNode[] reversed = reverseK(cur.next, k);
            ListNode newHead = reversed[0];
            ListNode oldHead = reversed[1];

            // 接回原链表
            cur.next = newHead;
            oldHead.next = ne;
            cur = oldHead;

            n -= k;
        }

        return dummy.next;
    }

    private ListNode[] reverseK(ListNode head, int k) {
        /* 反转前 k 个节点，返回 [新头, 旧头] */
        ListNode oldHead = head;
        ListNode pre = null, cur = head;
        while (k > 0) {
            ListNode ne = cur.next;
            cur.next = pre;
            pre = cur;
            cur = ne;
            k--;
        }
        return new ListNode[]{pre, oldHead};
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点被遍历和反转各一次
• 空间复杂度：O(1) — 仅用指针变量

LeetCode 138. 随机链表的复制

难度：⭐⭐ 中等  |  标签：链表 哈希表

🔗 LeetCode 原题链接

---

核心思路

由于 random 指针的存在，需要两趟遍历：

1. 第一趟（复制结点）：遍历原链表，为每个结点创建拷贝，存入哈希表 原结点 → 拷贝结点
2. 第二趟（复制边）：再次遍历原链表，利用哈希表设置拷贝结点的 next 和 random

哈希表中预先存入 {None: None}，这样访问 dic[cur.next] 或 dic[cur.random] 为 None 时也能正确映射。

PythonJava

from typing import Optional, Dict

# Definition for a Node.
# class Node:
#     def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
#         self.val = int(x)
#         self.next = next
#         self.random = random

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        # 1. 复制所有结点
        dic: Dict[Optional[Node], Optional[Node]] = {None: None}
        cur = head
        while cur:
            dic[cur] = Node(cur.val)
            cur = cur.next

        # 2. 复制边
        cur = head
        while cur:
            dic[cur].next = dic[cur.next]
            dic[cur].random = dic[cur.random]
            cur = cur.next

        return dic[head]

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        // 1. 复制所有结点
        Map<Node, Node> map = new HashMap<>();
        map.put(null, null);
        Node cur = head;
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        // 2. 复制边
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
}

复杂度分析

• 时间复杂度：O(n) — 两次线性遍历
• 空间复杂度：O(n) — 哈希表存储原结点到拷贝结点的映射

LeetCode 23. 合并 K 个升序链表

难度：⭐⭐⭐ 困难  |  标签：链表 堆（优先队列） 分治 归并

🔗 LeetCode 原题链接

---

核心思路

多路归并，利用小根堆维护当前 k 个链表头的最小值：

1. 将所有非空链表头节点入堆
2. 每次弹出最小节点接到结果链表尾部，并将其 next 节点入堆
3. 重复直到堆为空

Python 中需要为 ListNode 注入 __lt__ 方法才能比较；Java 的 PriorityQueue 通过 Lambda 指定比较器即可。

PythonJava

from typing import Optional, List
import heapq

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

ListNode.__lt__ = lambda x, y: x.val < y.val

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 小根堆
        heap = []
        for cur in lists:
            if cur:
                heapq.heappush(heap, cur)

        # 多路归并
        dummy = ListNode(-1)
        tail = dummy
        while heap:
            cur = heapq.heappop(heap)
            tail.next = cur
            tail = tail.next

            if cur.next:
                heapq.heappush(heap, cur.next)

        return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>(
            (a, b) -> a.val - b.val
        );
        for (ListNode node : lists) {
            if (node != null) {
                heap.offer(node);
            }
        }

        // 多路归并
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            tail.next = cur;
            tail = tail.next;

            if (cur.next != null) {
                heap.offer(cur.next);
            }
        }

        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(n log k) — 每个节点入堆出堆各一次，堆操作 O(log k)，k 为链表数量
• 空间复杂度：O(k) — 堆中最多同时存放 k 个节点

LeetCode 146. LRU 缓存

难度：⭐⭐ 中等  |  标签：设计 链表 哈希表 双向链表

🔗 LeetCode 原题链接

---

核心思路

用 HashMap + 双向链表 实现 O(1) 的 get 和 put：

• HashMap：key → Node，O(1) 查找
• 双向链表：维护访问顺序，头结点最近被使用，尾结点最久未使用
• get / put 时都将对应结点移到链表头部（先删除再在 head 右边插入）
• 超出容量时，删除链表尾部结点，同时从 HashMap 中移除

PythonJava

class LRUCache:

    class Node:
        def __init__(self, key, val, pre=None, next=None):
            self.key = key
            self.val = val
            self.pre = pre
            self.next = next

    class DoubleLinkedList:
        def __init__(self):
            self.head = LRUCache.Node(0, 0)
            self.tail = LRUCache.Node(0, 0)
            self.head.next = self.tail
            self.tail.pre = self.head

        def add_node_right(self, cur, node):
            """在 cur 结点右边插入 node"""
            node.next = cur.next
            node.pre = cur
            cur.next.pre = node
            cur.next = node

        def remove_cur(self, cur):
            """从链表中删除 cur 结点"""
            cur.next.pre = cur.pre
            cur.pre.next = cur.next

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.doubleList = LRUCache.DoubleLinkedList()

    def get(self, key: int) -> int:
        if key in self.cache:
            cur = self.cache[key]
            # 移到链表头部（先删除再插入到 head 右边）
            self.doubleList.remove_cur(cur)
            self.doubleList.add_node_right(self.doubleList.head, cur)
            return cur.val
        return -1

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            node = LRUCache.Node(key, value)
            self.cache[key] = node
            self.doubleList.add_node_right(self.doubleList.head, node)
            if len(self.cache) > self.capacity:
                # 删除最久未使用的（尾部结点）
                del_node = self.doubleList.tail.pre
                self.doubleList.remove_cur(del_node)
                del self.cache[del_node.key]
        else:
            node = self.cache[key]
            node.val = value
            # 移到链表头部
            self.doubleList.remove_cur(node)
            self.doubleList.add_node_right(self.doubleList.head, node)

class LRUCache {

    class Node {
        int key, val;
        Node pre, next;
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private int capacity;
    private Map<Integer, Node> cache;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        // 虚拟头尾结点
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            Node cur = cache.get(key);
            // 移到链表头部
            removeNode(cur);
            addToHead(cur);
            return cur.val;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (!cache.containsKey(key)) {
            Node node = new Node(key, value);
            cache.put(key, node);
            addToHead(node);
            if (cache.size() > capacity) {
                // 删除最久未使用的（尾部结点）
                Node delNode = tail.pre;
                removeNode(delNode);
                cache.remove(delNode.key);
            }
        } else {
            Node node = cache.get(key);
            node.val = value;
            // 移到链表头部
            removeNode(node);
            addToHead(node);
        }
    }

    private void removeNode(Node cur) {
        cur.pre.next = cur.next;
        cur.next.pre = cur.pre;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }
}

复杂度分析

• 时间复杂度：O(1) — get 和 put 均为 O(1)
• 空间复杂度：O(capacity) — 哈希表 + 双向链表存储所有缓存结点

LeetCode 94. 二叉树的中序遍历

难度：⭐ 简单  |  标签：二叉树 栈 迭代

🔗 LeetCode 原题链接

---

核心思路

非递归遍历，用栈模拟递归过程：

• 一直往左走，沿途节点入栈
• 走到 null 后弹出栈顶，记录值，然后转向右子树
• 重复直到栈为空且当前节点为 null

PythonJava

from typing import Optional, List

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stk, res = [], []

        while root or stk:
            # 一路向左，入栈
            while root:
                stk.append(root)
                root = root.left

            # 弹出栈顶，访问，转向右子树
            root = stk.pop()
            res.append(root.val)
            root = root.right

        return res

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stk = new ArrayDeque<>();

        while (root != null || !stk.isEmpty()) {
            // 一路向左，入栈
            while (root != null) {
                stk.push(root);
                root = root.left;
            }

            // 弹出栈顶，访问，转向右子树
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }

        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点恰好入栈出栈一次
• 空间复杂度：O(h) — 栈深度取决于树高 h，最坏 O(n)

LeetCode 104. 二叉树的最大深度

难度：⭐ 简单  |  标签：二叉树 递归 DFS

🔗 LeetCode 原题链接

---

核心思路

分治递归：

• 空节点深度为 0
• 当前节点的深度 = 左右子树最大深度 + 1

本质上是后序遍历（DFS），先递归求左右深度，再合并。

PythonJava

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点访问一次
• 空间复杂度：O(h) — 递归栈深度取决于树高 h，最坏 O(n)

LeetCode 226. 翻转二叉树

难度：⭐ 简单  |  标签：二叉树 递归 DFS

🔗 LeetCode 原题链接

---

核心思路

后序遍历 + 交换左右子树：

• 递归翻转左右子树
• 然后将当前节点的左右子树交换
• 空节点直接返回 null

PythonJava

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left = right
        root.right = left
        return root

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点访问一次
• 空间复杂度：O(h) — 递归栈深度取决于树高 h，最坏 O(n)

LeetCode 101. 对称二叉树

难度：⭐ 简单  |  标签：二叉树 递归 DFS

🔗 LeetCode 原题链接

---

核心思路

判断左右子树是否互为镜像：

• 两个空节点 → 对称
• 一个为空一个不为空 → 不对称
• 值相等 + 左左 vs 右右 + 左右 vs 右左 都对称 → 对称

PythonJava

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return self.isMirror(root.left, root.right)

    def isMirror(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val
                and self.isMirror(left.left, right.right)
                and self.isMirror(left.right, right.left))

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return left.val == right.val
                && isMirror(left.left, right.right)
                && isMirror(left.right, right.left);
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点访问一次
• 空间复杂度：O(h) — 递归栈深度取决于树高 h，最坏 O(n)

LeetCode 543. 二叉树的直径

难度：⭐ 简单  |  标签：二叉树 递归 DFS

🔗 LeetCode 原题链接

---

核心思路

直径 = 任意两节点间最长路径的边数，不一定经过根节点。

在 DFS 后序遍历过程中：

• 对于每个节点，经过它的最长直径 = 左子树高度 + 右子树高度
• 全局变量 res 记录最大值
• 返回当前子树的高度 = max(left, right) + 1

PythonJava

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def diameterOfBinaryTree(self, _root: Optional[TreeNode]) -> int:
        res = 0

        def dfs(root: Optional[TreeNode]) -> int:
            nonlocal res
            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            res = max(res, left + right)
            return max(left, right) + 1

        dfs(_root)
        return res

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int res = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        res = Math.max(res, left + right);
        return Math.max(left, right) + 1;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点访问一次
• 空间复杂度：O(h) — 递归栈深度取决于树高 h，最坏 O(n)

LeetCode 102. 二叉树的层序遍历

难度：⭐⭐ 中等  |  标签：二叉树 BFS 队列

🔗 LeetCode 原题链接

---

核心思路

经典 BFS，逐层遍历：

• 根节点入队
• 每次取出当前层的所有节点（通过 len(q) / q.size() 控制次数）
• 收集值的同时将左右子节点加入队列，准备下一层

PythonJava

from typing import Optional, List
from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        q, res = deque(), []
        if not root:
            return res

        q.append(root)
        while q:
            size = len(q)
            layer = []
            while size:
                size -= 1
                front = q.popleft()
                layer.append(front.val)
                if front.left:
                    q.append(front.left)
                if front.right:
                    q.append(front.right)
            res.append(layer)

        return res

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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> layer = new ArrayList<>();
            while (size > 0) {
                size--;
                TreeNode front = q.poll();
                layer.add(front.val);
                if (front.left != null) q.offer(front.left);
                if (front.right != null) q.offer(front.right);
            }
            res.add(layer);
        }

        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点入队出队各一次
• 空间复杂度：O(n) — 队列最多存储一层的节点，最坏 O(n)

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

难度：⭐ 简单  |  标签：二叉树 二叉搜索树 分治 递归

🔗 LeetCode 原题链接

---

核心思路

取数组中间元素作为根节点，左右部分递归构造：

• 选取 mid = (l + r) // 2 作为根
• 左半部分 [l, mid-1] 递归构造左子树
• 右半部分 [mid+1, r] 递归构造右子树
• 这样构造出的 BST 一定是平衡的（高度差 ≤ 1）

PythonJava

from typing import List, Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid + 1:])
        return root

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(int[] nums, int l, int r) {
        if (l > r) return null;
        int mid = (l + r) >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, l, mid - 1);
        root.right = build(nums, mid + 1, r);
        return root;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个元素恰好构造一个节点
• 空间复杂度：O(log n) — 递归栈深度为平衡树高 O(log n)

LeetCode 98. 验证二叉搜索树

难度：⭐⭐ 中等  |  标签：二叉树 二叉搜索树 递归 中序遍历

🔗 LeetCode 原题链接

---

核心思路

BST 的中序遍历结果严格递增，利用这一性质用递归验证：

• 维护一个全局变量 pre，记录中序遍历中上一个节点的值
• 递归左子树，若返回 false 则提前退出
• 判断当前节点值是否 ≤ pre，是则非法
• 更新 pre 为当前值，继续递归右子树

边界处理

初始 pre 设为 -inf（Python 用 float('-inf')，Java 用 Long.MIN_VALUE），防止节点值恰好为 Integer.MIN_VALUE 时误判。

PythonJava

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def __init__(self):
        self.pre = float('-inf')

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        if not self.isValidBST(root.left):
            return False
        if root.val <= self.pre:
            return False
        self.pre = root.val
        return self.isValidBST(root.right)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (root.val <= pre) return false;
        pre = root.val;
        return isValidBST(root.right);
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点访问一次
• 空间复杂度：O(h) — 递归栈深度取决于树高 h，最坏 O(n)

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

难度：⭐⭐ 中等  |  标签：二叉搜索树 中序遍历 栈

🔗 LeetCode 原题链接

---

核心思路

BST 的中序遍历结果是有序的，利用栈模拟中序遍历，找到第 k 个即返回：

• 一直往左走，沿途节点入栈
• 弹出栈顶，计数减 1，若计数为 0 则返回当前节点值
• 转向右子树继续

PythonJava

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stk = []
        while root or stk:
            while root:
                stk.append(root)
                root = root.left

            root = stk.pop()
            k -= 1
            if k == 0:
                return root.val

            root = root.right

        return -1

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stk = new ArrayDeque<>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            k--;
            if (k == 0) return root.val;
            root = root.right;
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O(n) — 最坏需遍历到第 k 个节点
• 空间复杂度：O(h) — 栈深度取决于树高 h，最坏 O(n)

LeetCode 199. 二叉树的右视图

难度：⭐⭐ 中等  |  标签：二叉树 BFS 层序遍历

🔗 LeetCode 原题链接

---

核心思路

BFS 层序遍历，每层最后一个节点即为右视图看到的节点：

• 根节点入队
• 每次处理一层，当 size 减到 0 时，当前节点就是该层最右节点，记录值
• 按顺序将左右子节点入队

PythonJava

from typing import Optional, List
from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        res, q = [], deque()
        q.append(root)

        while q:
            size = len(q)
            while size:
                size -= 1
                cur = q.popleft()
                if not size:          # 当前层最后一个节点
                    res.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)

        return res

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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();
            while (size > 0) {
                size--;
                TreeNode cur = q.poll();
                if (size == 0) {          // 当前层最后一个节点
                    res.add(cur.val);
                }
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
        }

        return res;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点访问一次
• 空间复杂度：O(n) — 队列最多存储一层的节点

LeetCode 114. 二叉树展开为链表

难度：⭐⭐ 中等  |  标签：二叉树 递归 DFS 后序遍历

🔗 LeetCode 原题链接

---

核心思路

将二叉树按先序遍历顺序展开为链表（右指针 → next，左指针置空）。

使用后序遍历（右 → 左 → 根）配合全局变量 pre 实现 O(1) 额外空间：

• 递归顺序：先右子树，再左子树，最后根节点
• 每访问一个节点：root.left = None; root.right = pre; pre = root
• 这样从后往前构建链表，巧妙地符合了先序顺序

PythonJava

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def flatten(self, _root: Optional[TreeNode]) -> None:
        pre = None

        def dfs(root: Optional[TreeNode]) -> None:
            nonlocal pre
            if not root:
                return
            dfs(root.right)
            dfs(root.left)
            root.left = None
            root.right = pre
            pre = root

        dfs(_root)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode pre = null;

    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.left = null;
        root.right = pre;
        pre = root;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点访问一次
• 空间复杂度：O(h) — 递归栈深度取决于树高 h，最坏 O(n)

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

难度：⭐⭐ 中等  |  标签：二叉树 递归 分治 哈希表

🔗 LeetCode 原题链接

---

核心思路

利用先序和中序遍历的性质分治构造：

• 先序：[根, 左子树, 右子树]
• 中序：[左子树, 根, 右子树]
• 用哈希表记录中序值到索引的映射，O(1) 查找根位置
• 左子树节点数 size = pos - l2，据此划分先序和中序的左右部分，递归构造

PythonJava

from typing import List, Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        dic = {val: i for i, val in enumerate(inorder)}

        def dfs(l1: int, r1: int, l2: int, r2: int) -> Optional[TreeNode]:
            if l1 > r1:
                return None

            root = preorder[l1]
            pos = dic[root]
            size = pos - l2  # 左子树节点数

            left = dfs(l1 + 1, l1 + size, l2, pos - 1)
            right = dfs(l1 + size + 1, r1, pos + 1, r2)

            return TreeNode(root, left, right)

        n = len(preorder)
        return dfs(0, n - 1, 0, n - 1)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<Integer, Integer> map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return dfs(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode dfs(int[] preorder, int l1, int r1, int l2, int r2) {
        if (l1 > r1) return null;

        int root = preorder[l1];
        int pos = map.get(root);
        int size = pos - l2;  // 左子树节点数

        TreeNode left = dfs(preorder, l1 + 1, l1 + size, l2, pos - 1);
        TreeNode right = dfs(preorder, l1 + size + 1, r1, pos + 1, r2);

        return new TreeNode(root, left, right);
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点构造一次，哈希表 O(1) 查找
• 空间复杂度：O(n) — 哈希表 + 递归栈空间

LeetCode 437. 路径总和 III

难度：⭐⭐ 中等  |  标签：二叉树 前缀和 哈希表 回溯

🔗 LeetCode 原题链接

---

核心思路

将路径和问题转化为前缀和思想（类似 [[560]] 和为 K 的子数组），应用到树上：

• DFS 遍历过程中维护当前路径和 sum 及前缀和字典 cnt
• 对于当前节点，need = sum - targetSum，cnt[need] 即为以该节点为结尾的合法路径数
• 递归完左右子树后回溯，恢复 cnt[sum] 和 sum

PythonJava

from typing import Optional
from collections import defaultdict

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        sum, cnt, res = 0, defaultdict(int), 0
        cnt[0] = 1

        def dfs(cur: Optional[TreeNode]) -> None:
            nonlocal res, sum
            if not cur:
                return

            sum += cur.val
            need = sum - targetSum
            res += cnt[need]
            cnt[sum] += 1

            dfs(cur.left)
            dfs(cur.right)

            # 回溯
            cnt[sum] -= 1
            sum -= cur.val

        dfs(root)
        return res

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int res = 0;
    private int sum = 0;
    private Map<Integer, Integer> cnt = new HashMap<>();

    public int pathSum(TreeNode root, int targetSum) {
        cnt.put(0, 1);
        dfs(root, targetSum);
        return res;
    }

    private void dfs(TreeNode root, int targetSum) {
        if (root == null) return;

        sum += root.val;
        int need = sum - targetSum;
        res += cnt.getOrDefault(need, 0);
        cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);

        dfs(root.left, targetSum);
        dfs(root.right, targetSum);

        // 回溯
        cnt.put(sum, cnt.get(sum) - 1);
        sum -= root.val;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点访问一次
• 空间复杂度：O(n) — 前缀和哈希表 + 递归栈空间

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

难度：⭐⭐ 中等  |  标签：二叉树 递归 DFS

🔗 LeetCode 原题链接

---

核心思路

后序遍历 + 分治判断：

• 若当前节点为 null，返回 null
• 若当前节点等于 p 或 q，直接返回当前节点（找到了）
• 递归在左右子树中查找 p、q
• 分情况讨论：
  • 左子树为空 → LCA 在右子树
  • 右子树为空 → LCA 在左子树
  • 左右都不为空 → 当前节点就是 LCA

PythonJava

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        if root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if not left:
            return right
        if not right:
            return left

        return root

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if (left == null) return right;
        if (right == null) return left;

        return root;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点访问一次
• 空间复杂度：O(h) — 递归栈深度取决于树高 h，最坏 O(n)

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

难度：⭐⭐⭐ 困难  |  标签：二叉树 递归 DFS 后序遍历

🔗 LeetCode 原题链接

---

核心思路

后序遍历，每个节点返回从该节点往下走的最大贡献值，同时更新全局最大值：

• 空节点贡献为 0
• 左右子树的负贡献直接丢弃（取 max(0, gain)）
• 经过当前节点的最大路径和 = cur.val + max(0, left_gain) + max(0, right_gain)
• 返回给父节点的贡献 = cur.val + max(0, left_gain, right_gain)（只能选一边，路径不能分叉）

PythonJava

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        res = float('-inf')

        def dfs(cur: Optional[TreeNode]) -> int:
            nonlocal res
            if not cur:
                return 0

            l = dfs(cur.left)
            r = dfs(cur.right)

            # 经过当前节点的最大路径和
            cur_max = max(cur.val, cur.val + max(0, l) + max(0, r))
            res = max(res, cur_max)

            # 返回从当前节点往下走的最大贡献（只能选一边）
            return max(cur.val + max(0, l), cur.val + max(0, r))

        dfs(root)
        return res

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode root) {
        if (root == null) return 0;

        int left = dfs(root.left);
        int right = dfs(root.right);

        // 经过当前节点的最大路径和
        int curMax = Math.max(root.val, root.val + Math.max(0, left) + Math.max(0, right));
        res = Math.max(res, curMax);

        // 返回从当前节点往下走的最大贡献（只能选一边）
        return Math.max(root.val + Math.max(0, left), root.val + Math.max(0, right));
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个节点访问一次
• 空间复杂度：O(h) — 递归栈深度取决于树高 h，最坏 O(n)

LeetCode 200. 岛屿数量

难度：⭐⭐ 中等  |  标签：数组 矩阵 DFS BFS

🔗 LeetCode 原题链接

---

核心思路

DFS 洪水填充（Flood Fill）：

• 遍历网格，遇到 '1' 即发现一个新岛屿，计数 +1
• 从该位置 DFS，将相连的所有 '1' 标记为已访问（'x'）
• DFS 沿四个方向（上、下、左、右）扩散

PythonJava

from typing import List

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        n, m = len(grid), len(grid[0])
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def dfs(x: int, y: int) -> None:
            grid[x][y] = 'x'
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if nx < 0 or nx >= n or ny < 0 or ny >= m or grid[nx][ny] != '1':
                    continue
                dfs(nx, ny)

        res = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1':
                    dfs(i, j)
                    res += 1

        return res

class Solution {
    public int numIslands(char[][] grid) {
        int n = grid.length, m = grid[0].length;
        int res = 0;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs(grid, i, j, dirs);
                }
            }
        }
        return res;
    }

    private void dfs(char[][] grid, int x, int y, int[][] dirs) {
        int n = grid.length, m = grid[0].length;
        grid[x][y] = 'x';
        for (int[] d : dirs) {
            int nx = x + d[0], ny = y + d[1];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] != '1') continue;
            dfs(grid, nx, ny, dirs);
        }
    }
}

复杂度分析

• 时间复杂度：O(m × n) — 每个网格访问一次
• 空间复杂度：O(m × n) — 最坏情况下递归栈深度为整个网格

LeetCode 994. 腐烂的橘子

难度：⭐⭐ 中等  |  标签：数组 矩阵 BFS

🔗 LeetCode 原题链接

---

核心思路

多源 BFS（类似层序遍历）：

• 初始将所有腐烂橘子入队，同时统计新鲜橘子数量
• 每一分钟，当前队列中所有腐烂橘子同时向四周扩散（按层 BFS）
• 每感染一个新鲜橘子，新鲜数减 1，若变为 0 则提前返回当前分钟数
• 队列为空后若还有新鲜橘子，返回 -1

PythonJava

from typing import List
from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        fresh = 0
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        q = deque()

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 2:
                    q.append((i, j))
                elif grid[i][j] == 1:
                    fresh += 1

        if fresh == 0:
            return 0

        res = 0
        while q:
            res += 1
            for _ in range(len(q)):
                x, y = q.popleft()
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if nx < 0 or nx >= n or ny < 0 or ny >= m or grid[nx][ny] != 1:
                        continue
                    grid[nx][ny] = 2
                    fresh -= 1
                    q.append((nx, ny))
                    if fresh == 0:
                        return res

        return -1 if fresh != 0 else res

class Solution {
    public int orangesRotting(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int fresh = 0;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Queue<int[]> q = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    q.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }

        if (fresh == 0) return 0;

        int res = 0;
        while (!q.isEmpty()) {
            res++;
            int size = q.size();
            for (int k = 0; k < size; k++) {
                int[] cur = q.poll();
                int x = cur[0], y = cur[1];
                for (int[] d : dirs) {
                    int nx = x + d[0], ny = y + d[1];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] != 1) continue;
                    grid[nx][ny] = 2;
                    fresh--;
                    q.offer(new int[]{nx, ny});
                    if (fresh == 0) return res;
                }
            }
        }

        return fresh != 0 ? -1 : res;
    }
}

复杂度分析

• 时间复杂度：O(m × n) — 每个网格访问一次
• 空间复杂度：O(m × n) — 队列最多存储所有腐烂橘子

LeetCode 207. 课程表

难度：⭐⭐ 中等  |  标签：图 拓扑排序 BFS

🔗 LeetCode 原题链接

---

核心思路

判断有向图是否存在拓扑排序（即无环）：

• 用邻接表建图，同时统计每个节点的入度
• 将所有入度为 0 的节点入队（它们没有前置依赖）
• BFS 遍历：弹出节点，将其所有邻接节点的入度减 1，若变为 0 则入队
• 最后检查入队节点数是否等于总课程数

PythonJava

from typing import List
from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 邻接表 + 入度数组
        g = [[] for _ in range(numCourses)]
        d = [0] * numCourses
        q, res = deque(), []

        # 建图
        for a, b in prerequisites:
            g[b].append(a)
            d[a] += 1

        # 初始入度为 0 的节点入队
        for i in range(numCourses):
            if d[i] == 0:
                q.append(i)
                res.append(i)

        # BFS 拓扑排序
        while q:
            cur = q.popleft()
            for ne in g[cur]:
                d[ne] -= 1
                if d[ne] == 0:
                    q.append(ne)
                    res.append(ne)

        return len(res) == numCourses

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 邻接表 + 入度数组
        List<Integer>[] g = new List[numCourses];
        int[] d = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i] = new ArrayList<>();
        }

        // 建图
        for (int[] p : prerequisites) {
            int a = p[0], b = p[1];
            g[b].add(a);
            d[a]++;
        }

        // 初始入度为 0 的节点入队
        Queue<Integer> q = new ArrayDeque<>();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (d[i] == 0) {
                q.offer(i);
                res.add(i);
            }
        }

        // BFS 拓扑排序
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int ne : g[cur]) {
                d[ne]--;
                if (d[ne] == 0) {
                    q.offer(ne);
                    res.add(ne);
                }
            }
        }

        return res.size() == numCourses;
    }
}

复杂度分析

• 时间复杂度：O(V + E) — V 为课程数，E 为先修关系数
• 空间复杂度：O(V + E) — 邻接表 + 入度数组

LeetCode 208. 实现 Trie (前缀树)

难度：⭐⭐ 中等  |  标签：设计 字典树 Trie

🔗 LeetCode 原题链接

---

核心思路

Trie 树的核心是利用字符串公共前缀来减少查询时间：

• 每个节点有 26 个子节点指针（对应小写字母 a-z）
• is_end：标记从根到该节点是否构成一个完整单词
• is_pre：标记是否有单词经过该节点（用于前缀查询）
• insert：逐字符遍历，不存在则创建新节点
• search：逐字符查找，最后检查 is_end
• startsWith：逐字符查找，最后检查 is_pre

PythonJava

class Trie:

    class Node:
        def __init__(self):
            self.children = [None] * 26
            self.is_end = False
            self.is_pre = False

    def __init__(self):
        self.root = self.Node()

    def insert(self, word: str) -> None:
        p = self.root
        for c in word:
            u = ord(c) - ord('a')
            if not p.children[u]:
                p.children[u] = self.Node()
            p = p.children[u]
            p.is_pre = True
        p.is_end = True

    def search(self, word: str) -> bool:
        p = self.root
        for c in word:
            u = ord(c) - ord('a')
            if not p.children[u]:
                return False
            p = p.children[u]
        return p.is_end

    def startsWith(self, prefix: str) -> bool:
        p = self.root
        for c in prefix:
            u = ord(c) - ord('a')
            if not p.children[u]:
                return False
            p = p.children[u]
        return p.is_pre

class Trie {

    class Node {
        Node[] children = new Node[26];
        boolean isEnd = false;
        boolean isPre = false;
    }

    private Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node p = root;
        for (char c : word.toCharArray()) {
            int u = c - 'a';
            if (p.children[u] == null) {
                p.children[u] = new Node();
            }
            p = p.children[u];
            p.isPre = true;
        }
        p.isEnd = true;
    }

    public boolean search(String word) {
        Node p = root;
        for (char c : word.toCharArray()) {
            int u = c - 'a';
            if (p.children[u] == null) return false;
            p = p.children[u];
        }
        return p.isEnd;
    }

    public boolean startsWith(String prefix) {
        Node p = root;
        for (char c : prefix.toCharArray()) {
            int u = c - 'a';
            if (p.children[u] == null) return false;
            p = p.children[u];
        }
        return p.isPre;
    }
}

复杂度分析

• 时间复杂度：O(L) — 每次操作仅遍历单词长度 L
• 空间复杂度：O(ΣL) — Σ 为所有插入单词的总字符数

LeetCode 46. 全排列

难度：⭐⭐ 中等  |  标签：回溯 数组

🔗 LeetCode 原题链接

---

核心思路

回溯（DFS）经典入门题。外层 dfs(u) 遍历的是每个位置，内层 for 遍历的是当前位置可以放哪些数，通过 used 数组标记已选数字，从而实现不重不漏。

• 用一个 used 数组标记哪些元素已被使用
• 当 u == n 时，所有位置都已填满，记录当前排列

PythonJava

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res, path = [], []
        used = [False] * n

        def dfs(u: int) -> None:
            if u == n:
                res.append(path[:])
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                path.append(nums[i])
                dfs(u + 1)
                path.pop()
                used[i] = False

        dfs(0)
        return res

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[n];
        dfs(nums, used, path, res);
        return res;
    }

    private void dfs(int[] nums, boolean[] used,
                     List<Integer> path, List<List<Integer>> res) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(nums[i]);
            dfs(nums, used, path, res);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

复杂度分析

• 时间复杂度：O(n × n!) — 全排列共有 n! 种，每种需 O(n) 复制到结果集
• 空间复杂度：O(n) — 递归栈深度 n，used 数组和 path 各 O(n)

LeetCode 78. 子集

难度：⭐⭐ 中等  |  标签：回溯 数组 位运算

🔗 LeetCode 原题链接

---

核心思路

每个元素都有两种选择：选 或 不选，DFS 遍历所有组合即可。

• 先选当前元素进入 path，递归下一个位置
• 回溯撤销选择（path.pop()），再递归下一个位置（不选）
• 当 cur == n 时所有元素处理完毕，记录当前子集

相比全排列，子集不需要 used 数组 —— 因为每个位置只有「选/不选」两种固定选择，不会重复。

PythonJava

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res, path = [], []
        n = len(nums)

        def dfs(cur: int) -> None:
            if cur == n:
                res.append(path[:])
                return
            # 选当前元素
            path.append(nums[cur])
            dfs(cur + 1)
            # 不选当前元素
            path.pop()
            dfs(cur + 1)

        dfs(0)
        return res

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(nums, 0, path, res);
        return res;
    }

    private void dfs(int[] nums, int cur,
                     List<Integer> path, List<List<Integer>> res) {
        if (cur == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 选当前元素
        path.add(nums[cur]);
        dfs(nums, cur + 1, path, res);
        // 不选当前元素
        path.remove(path.size() - 1);
        dfs(nums, cur + 1, path, res);
    }
}

复杂度分析

• 时间复杂度：O(n × 2ⁿ) — 每个元素选/不选共 2ⁿ 个子集，每个需 O(n) 复制到结果集
• 空间复杂度：O(n) — 递归栈深度 n，path 最多存储 n 个元素

LeetCode 17. 电话号码的字母组合

难度：⭐⭐ 中等  |  标签：回溯 哈希表 字符串

🔗 LeetCode 原题链接

---

核心思路

和全排列本质相同 —— 每个位置从固定候选项中选择一个字符。

• 用哈希表建立数字到字母集合的映射
• dfs(cur) 表示正在处理第 cur 个数字
• 内层 for 遍历当前数字对应的所有字母，选一个进入下一层
• 当 cur == n 时所有数字处理完毕，记录当前组合

边界条件

当 digits 为空字符串时，直接返回空列表 []，而不是 [""]。

PythonJava

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        dic = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }
        res, path = [], []
        n = len(digits)

        def dfs(cur: int) -> None:
            if cur == n:
                res.append(''.join(path))
                return
            for c in dic[digits[cur]]:
                path.append(c)
                dfs(cur + 1)
                path.pop()

        dfs(0)
        return res

class Solution {
    private static final Map<Character, String> MAP = Map.of(
        '2', "abc", '3', "def", '4', "ghi", '5', "jkl",
        '6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz"
    );

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.isEmpty()) return List.of();
        List<String> res = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        dfs(digits, 0, path, res);
        return res;
    }

    private void dfs(String digits, int cur,
                     StringBuilder path, List<String> res) {
        if (cur == digits.length()) {
            res.add(path.toString());
            return;
        }
        String letters = MAP.get(digits.charAt(cur));
        for (char c : letters.toCharArray()) {
            path.append(c);
            dfs(digits, cur + 1, path, res);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

复杂度分析

• 时间复杂度：O(4ⁿ × n) — 最坏情况每个数字对应 4 个字母（7/9），共 4ⁿ 种组合，拼接结果 O(n)
• 空间复杂度：O(n) — 递归栈深度 n，path 最多存储 n 个字符

LeetCode 39. 组合总和

难度：⭐⭐ 中等  |  标签：回溯 数组

🔗 LeetCode 原题链接

---

核心思路

每个数可以无限重复选取，关键在递归时控制索引移动：

• 选当前数：total + candidates[cur]，递归时 cur 不移动（因为可以重复选）
• 不选当前数：cur + 1 跳到下一个数，total 不变
• 剪枝：当 total > target 或 cur == n 时提前返回

与子集不同的是：这里「不选」分支负责跳到下一个元素（因为可以无限选），而非子集中的选完再回溯。

PythonJava

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res, path = [], []
        n = len(candidates)

        def dfs(cur: int, total: int) -> None:
            if total == target:
                res.append(path[:])
                return
            if cur == n or total > target:
                return

            # 选当前数（可以无限重复，cur 不动）
            path.append(candidates[cur])
            dfs(cur, total + candidates[cur])
            path.pop()

            # 不选当前数，跳到下一个
            dfs(cur + 1, total)

        dfs(0, 0)
        return res

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(candidates, target, 0, 0, path, res);
        return res;
    }

    private void dfs(int[] candidates, int target, int cur, int sum,
                     List<Integer> path, List<List<Integer>> res) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (cur == candidates.length || sum > target) return;

        // 选当前数，cur 不移动（可重复选）
        path.add(candidates[cur]);
        dfs(candidates, target, cur, sum + candidates[cur], path, res);
        path.remove(path.size() - 1);

        // 不选当前数，跳到下一个
        dfs(candidates, target, cur + 1, sum, path, res);
    }
}

复杂度分析

• 时间复杂度：O(n^(t/m+1)) — 递归树深度为 target/min(candidates)，每层最多 n 个分支
• 空间复杂度：O(t/m) — 递归栈深度取决于最坏组合次数

LeetCode 22. 括号生成

难度：⭐⭐ 中等  |  标签：回溯 字符串 动态规划

🔗 LeetCode 原题链接

---

核心思路

看作填一个长度为 2n 的序列，每个位置有两种选择 —— 放左括号 ( 或 右括号 )，本质上是一棵二叉树的 DFS 遍历。

朴素做法是 2^(2n) 全枚举后筛选合法串，但可以通过 剪枝 在 DFS 过程中提前砍掉非法分支：

• l < r：右括号数量超过左括号，违反「任意前缀左括号数 ≥ 右括号数」规则，剪掉
• l > n：左括号用超了，剪掉
• r > n：右括号用超了，剪掉
• 终止条件：l == n and r == n，左右括号恰好各 n 个，加入结果

剪枝后实际访问的节点数等价于第 n 个 卡特兰数 \(C_n = \dfrac{1}{n+1}\dbinom{2n}{n}\)。

为什么剪枝条件是 l < r？

合法括号串的充要条件是：从左往右扫描时，左括号的数量始终 ≥ 右括号的数量（否则会出现 )(" 这种非法前缀）。

所以一旦在递归路径中 r > l，说明当前前缀已经非法，无需继续往下走。

PythonJava

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res, path = [], []

        def dfs(l: int, r: int) -> None:
            # 剪枝：前缀非法 或 数量超限
            if l < r or l > n or r > n:
                return
            # 终止：左右括号各 n 个
            if l == n and r == n:
                res.append(''.join(path))
                return

            # 选左括号
            path.append('(')
            dfs(l + 1, r)
            path.pop()

            # 选右括号
            path.append(')')
            dfs(l, r + 1)
            path.pop()

        dfs(0, 0)
        return res

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        dfs(n, 0, 0, path, res);
        return res;
    }

    private void dfs(int n, int l, int r,
                     StringBuilder path, List<String> res) {
        // 剪枝：前缀非法 或 数量超限
        if (l < r || l > n || r > n) return;
        // 终止：左右括号各 n 个
        if (l == n && r == n) {
            res.add(path.toString());
            return;
        }

        // 选左括号
        path.append('(');
        dfs(n, l + 1, r, path, res);
        path.deleteCharAt(path.length() - 1);

        // 选右括号
        path.append(')');
        dfs(n, l, r + 1, path, res);
        path.deleteCharAt(path.length() - 1);
    }
}

复杂度分析

• 时间复杂度：O(Cₙ × n) — 其中 Cₙ 是第 n 个卡特兰数，访问每个合法节点 O(1)，拼接结果 O(n)
• 空间复杂度：O(n) — 递归栈深度 2n，path 最多存储 2n 个字符

LeetCode 79. 单词搜索

难度：⭐⭐ 中等  |  标签：回溯 矩阵 数组

🔗 LeetCode 原题链接

---

核心思路

二维矩阵上的路径搜索，本质是带状态回溯的 DFS：

• 起点不固定：必须遍历矩阵中每个格子 board[i][j]，依次作为起点尝试 dfs(i, j, 0)
• 四方向扩散：从当前格子向 上 / 下 / 左 / 右 四个方向继续匹配下一个字符
• 原地标记访问：将当前格子临时改为 #（或任意不可能同时出现在 board 和 word 中的字符），避免走回头路
• 回溯还原：递归返回前必须把格子改回原字符，让其他分支路径还能经过此格
• 早停优化：只要任一方向的 dfs 返回 True 就立即向上传递 True，无需探测剩余方向

为什么用 board[i][j] = '#' 而不是额外开 visited 数组？

原地修改省掉了 visited 数组的 O(MN) 额外空间，且判断「是否访问过」只需比较字符是否等于 #，代码更简洁。代价是会破坏原数组，所以这种写法不适用于需要保留原矩阵的场景（如 LeetCode 212 单词搜索 II 就常需要保留原矩阵去做 Trie 剪枝）。

PythonJava

from typing import List


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        dir = [(0, 1), (0, -1), (-1, 0), (1, 0)]
        n, m = len(board), len(board[0])

        def dfs(i: int, j: int, k: int) -> bool:
            if board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True

            # 标记当前位置访问过
            board[i][j] = '#'
            for dx, dy in dir:
                x, y = i + dx, j + dy
                if (0 <= x < n and 0 <= y < m
                        and board[x][y] != '#'
                        and dfs(x, y, k + 1)):
                    return True

            # 回溯：还原字符
            board[i][j] = word[k]
            return False

        for i in range(n):
            for j in range(m):
                if dfs(i, j, 0):
                    return True

        return False

class Solution {
    private static final int[][] DIR = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    public boolean exist(char[][] board, String word) {
        int n = board.length, m = board[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (dfs(board, word, i, j, 0, n, m)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word,
                        int i, int j, int k, int n, int m) {
        if (board[i][j] != word.charAt(k)) return false;
        if (k == word.length() - 1) return true;

        // 标记当前位置访问过
        board[i][j] = '#';
        for (int[] d : DIR) {
            int x = i + d[0], y = j + d[1];
            if (x >= 0 && x < n && y >= 0 && y < m
                    && board[x][y] != '#'
                    && dfs(board, word, x, y, k + 1, n, m)) {
                return true;
            }
        }

        // 回溯：还原字符
        board[i][j] = word.charAt(k);
        return false;
    }
}

复杂度分析

• 时间复杂度：O(MN × 4^L) — 最多从 MN 个格子出发，每个格子 DFS 深度为 L、每层最多 4 个方向（实际被 visited 剪枝后更少）
• 空间复杂度：O(L) — 递归栈深度 L（即 word 长度），原地修改省去了 visited 数组

LeetCode 131. 分割回文串

难度：⭐⭐ 中等  |  标签：回溯 字符串

🔗 LeetCode 原题链接

---

核心思路

两层枚举：外层 dfs(start) 隐式固定起点，内层 for 枚举当前这刀的终点。

• dfs(start) 表示从 start 开始切；start == n 说明切完，记录结果
• 取子串 s[start:i+1]，是回文才切，递归 dfs(i+1) 处理后半段
• 回溯时 path.pop()，尝试其他切法

PythonJava

from typing import List


class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res, path = [], []
        n = len(s)

        def dfs(start: int) -> None:
            if start == n:
                res.append(path[::])
                return

            # 枚举终点
            for i in range(start, n):
                sub = s[start:i + 1]
                if sub == sub[::-1]:  # 是回文才切
                    path.append(sub)
                    dfs(i + 1)
                    path.pop()

        dfs(0)
        return res

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(s, 0, s.length(), path, res);
        return res;
    }

    private void dfs(String s, int start, int n,
                     List<String> path, List<List<String>> res) {
        if (start == n) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < n; i++) {
            String sub = s.substring(start, i + 1);
            if (isPalindrome(sub)) {
                path.add(sub);
                dfs(s, i + 1, n, path, res);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s) {
        int l = 0, r = s.length() - 1;
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(n × 2ⁿ) — 共有 2^(n-1) 种切法，每次判回文最坏 O(n)
• 空间复杂度：O(n) — 递归栈深度 n，path 最多 n 个子串

LeetCode 51. N 皇后

难度：⭐⭐⭐ 困难  |  标签：回溯 数组

🔗 LeetCode 原题链接

---

核心思路

外层 dfs(row) 枚举行，内层 for 枚举当前行的每一列能否放皇后。判断能否放只看 列 / 两条对角线 三处是否冲突。

为了 O(1) 判断冲突，用三个布尔数组记录占用情况：

• col[j]：第 j 列是否被占
• gd[row + j]：正对角线（同行同对角线上 row + j 恒定）
• dg[row - j + n]：反对角线（同反对角线上 row - j 恒定，+ n 避免负下标）

三者都没被占才放皇后；回溯时三个数组都要还原。

为什么 k 参数其实是冗余的？

走到 row == n 时已经放了 n 行各 1 个皇后，k 必然等于 n，所以 if k == n 这个判断不会过滤掉任何合法解，留着只是为了"防御性"写法。实际面试可写可不写。

PythonJava

from typing import List


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res, gd, dg, col = [], [False] * (2 * n), [False] * (2 * n), [False] * n
        g = [['.'] * n for _ in range(n)]

        def dfs(row: int, k: int) -> None:
            if row == n:
                if k == n:
                    temp = []
                    for i in range(n):
                        temp.append(''.join(g[i]))
                    res.append(temp)
                return

            for j in range(n):
                if not col[j] and not gd[row + j] and not dg[row - j + n]:
                    g[row][j] = 'Q'
                    col[j] = gd[row + j] = dg[row - j + n] = True
                    dfs(row + 1, k + 1)
                    g[row][j] = '.'
                    col[j] = gd[row + j] = dg[row - j + n] = False

        dfs(0, 0)
        return res

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] g = new char[n][n];
        for (char[] r : g) Arrays.fill(r, '.');
        // 列、正对角线、反对角线
        boolean[] col = new boolean[n];
        boolean[] gd = new boolean[2 * n];   // row + j
        boolean[] dg = new boolean[2 * n];   // row - j + n
        dfs(g, 0, n, col, gd, dg, res);
        return res;
    }

    private void dfs(char[][] g, int row, int n,
                     boolean[] col, boolean[] gd, boolean[] dg,
                     List<List<String>> res) {
        if (row == n) {
            List<String> cur = new ArrayList<>();
            for (char[] r : g) cur.add(new String(r));
            res.add(cur);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (!col[j] && !gd[row + j] && !dg[row - j + n]) {
                g[row][j] = 'Q';
                col[j] = gd[row + j] = dg[row - j + n] = true;
                dfs(g, row + 1, n, col, gd, dg, res);
                g[row][j] = '.';
                col[j] = gd[row + j] = dg[row - j + n] = false;
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(n!) — 第 i 行最多 n-i+1 个选择，整棵搜索树接近 n!
• 空间复杂度：O(n²) — 棋盘 n² + 三个布尔数组 O(n) + 递归栈 O(n)

LeetCode 35. 搜索插入位置

难度：⭐ 简单  |  标签：二分查找 数组

🔗 LeetCode 原题链接

---

核心思路

标准二分，找 第一个 ≥ target 的位置。

易错点

• 区间右端是 n 而不是 n - 1：当 target 比所有元素都大时，应插入到末尾，下标就是 n
• 循环条件 l < r（左闭右开），命中分支 r = mid（不能 mid - 1，否则可能丢解）

PythonJava

from typing import List


class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l, r = 0, n
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        return l

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}

复杂度分析

• 时间复杂度：O(log n) — 标准二分
• 空间复杂度：O(1) — 只用了常数变量

LeetCode 74. 搜索二维矩阵

难度：⭐⭐ 中等  |  标签：二分查找 矩阵 数组

🔗 LeetCode 原题链接

---

核心思路

把 n × m 矩阵看成长度为 n × m 的有序一维数组，做存在性二分。

• 下标映射：一维 mid ↔ 二维 (mid // m, mid % m)
• 存在性二分：用 while l <= r（闭区间），命中直接返回 True
• 没命中时分支与普通二分一致：< 走右半 l = mid + 1，> 走左半 r = mid - 1

区分两种二分模板

• 存在性（找具体值）：l <= r，r 初值 n - 1
• 找边界（第一个/最后一个满足条件）：l < r，r 初值视情况可取 n

PythonJava

from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n, m = len(matrix), len(matrix[0])
        # 把二维矩阵映射为一维有序数组
        l, r = 0, n * m - 1
        while l <= r:
            mid = (l + r) >> 1
            x, y = mid // m, mid % m
            if matrix[x][y] == target:
                return True
            if matrix[x][y] < target:
                l = mid + 1
            else:
                r = mid - 1
        return False

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length;
        int l = 0, r = n * m - 1;
        while (l <= r) {
            int mid = (l + r) >>> 1;
            int x = mid / m, y = mid % m;
            if (matrix[x][y] == target) return true;
            if (matrix[x][y] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：O(log(n × m)) — 一维二分
• 空间复杂度：O(1) — 只用了常数变量

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

难度：⭐⭐ 中等  |  标签：二分查找 数组

🔗 LeetCode 原题链接

---

核心思路

两次二分，分别找 第一个 ≥ target 的位置 和 最后一个 ≤ target 的位置。

• 找左边界：标准 l < r，mid = (l + r) >> 1（下取整），命中目标后往左缩 r = mid
• 找右边界：l < r，mid = (l + r + 1) >> 1（上取整），命中目标后往右缩 l = mid
• 验证：两次结果都要判断 nums[pos] == target，不等说明 target 不存在，返回 -1

两个二分模板的区别

• 下取整 mid = l + r >> 1 + r = mid：适用于找 第一个 满足条件的
• 上取整 mid = l + r + 1 >> 1 + l = mid：适用于找 最后一个 满足条件的

混淆这两个模板会导致死循环或答案错误。

PythonJava

from typing import List


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        if not n:
            return [-1, -1]

        # 第一次出现的位置（第一个 >= target）
        l, r = 0, n - 1
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        first = l if nums[l] == target else -1

        # 最后一次出现的位置（最后一个 <= target）
        l, r = 0, n - 1
        while l < r:
            mid = (l + r + 1) >> 1
            if nums[mid] <= target:
                l = mid
            else:
                r = mid - 1
        last = l if nums[l] == target else -1

        return [first, last]

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return new int[]{-1, -1};

        // 第一次出现的位置
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int first = nums[l] == target ? l : -1;

        // 最后一次出现的位置
        l = 0; r = n - 1;
        while (l < r) {
            int mid = (l + r + 1) >>> 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        int last = nums[l] == target ? l : -1;

        return new int[]{first, last};
    }
}

复杂度分析

• 时间复杂度：O(log n) — 两次二分
• 空间复杂度：O(1) — 只用了常数变量

LeetCode 33. 搜索旋转排序数组

难度：⭐⭐ 中等  |  标签：二分查找 数组

🔗 LeetCode 原题链接

---

核心思路

旋转数组从中间切一刀，左右必有一边是有序的。判断 target 是否在有序的那半来缩小区间。

• 若 nums[l] <= nums[mid]：左半边有序
  • nums[l] <= target < nums[mid] → target 在左，r = mid - 1
  • 否则 → 在右，l = mid + 1
• 否则：右半边有序
  • nums[mid] < target <= nums[r] → target 在右，l = mid + 1
  • 否则 → 在左，r = mid - 1

易错点：<= 不能写成 <

判断左半有序时一定要用 nums[l] <= nums[mid]（带等号），否则当数组只有两个元素如 [3, 1] 时 l == mid、nums[l] < nums[mid] 为 False，两边都不命中，导致 死循环。

PythonJava

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l, r = 0, n - 1

        while l <= r:
            mid = (l + r) >> 1
            if nums[mid] == target:
                return mid

            # 左半有序
            if nums[l] <= nums[mid]:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            # 右半有序
            else:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1

        return -1

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;

        while (l <= r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] == target) return mid;

            // 左半有序
            if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            // 右半有序
            } else {
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O(log n) — 二分查找
• 空间复杂度：O(1) — 只用了常数变量

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

难度：⭐⭐ 中等  |  标签：二分查找 数组

🔗 LeetCode 原题链接

---

核心思路

利用 右端点 nums[n-1] 作为 pivot 做二分边界。旋转后数组的左半部分都 > nums[n-1]，右半部分都 <= nums[n-1]。

• 特判：nums[0] <= nums[n-1] 说明未旋转，直接返回 nums[0]
• 二分：找第一个 <= x（x = nums[n-1]）的位置
  • nums[mid] > x → 在左半部分，l = mid + 1
  • nums[mid] <= x → 在右半部分，r = mid

和 LeetCode 33 的区别

33 是 搜索具体值（存在性二分），用 while l <= r + 判断两侧有序性。 本题是 找边界（最小值位置），用 while l < r + 以 nums[n-1] 为标准划分左右区间。

PythonJava

from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        # 未旋转，第一个就是最小
        if nums[0] <= nums[n - 1]:
            return nums[0]

        l, r = 0, n - 1
        x = nums[r]  # 右端点作为 pivot
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] > x:
                l = mid + 1
            else:
                r = mid
        return nums[l]

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        // 未旋转，第一个就是最小
        if (nums[0] <= nums[n - 1]) return nums[0];

        int l = 0, r = n - 1;
        int x = nums[r];  // 右端点作为 pivot
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (nums[mid] > x) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[l];
    }
}

复杂度分析

• 时间复杂度：O(log n) — 二分查找
• 空间复杂度：O(1) — 只用了常数变量

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

难度：⭐⭐⭐ 困难  |  标签：二分查找 数组 分治

🔗 LeetCode 原题链接

---

核心思路

对较短的数组做二分切割，通过总数约束确定另一个数组的切割点，验证「左半全部 ≤ 右半全部」即可。

• 保证 n ≤ m：如果 nums1 更长则交换，确保二分范围是 [0, n]
• 切割点：i 切 nums1（[0, n]），j = (m + n + 1) // 2 - i 切 nums2
  • 左半总元素数 = (m + n + 1) // 2，右半自动补齐
• 边界处理：用 ±∞ 处理 i=0 / i=n / j=0 / j=m 的边界情况
• 验证合法：n1_lmax ≤ n2_rmin and n2_lmax ≤ n1_rmin
  • 合法 → 计算中位数（奇偶分别处理）
  • n1_lmax > n2_rmin → i 太大，左移 r = i - 1
  • 否则 → i 太小，右移 l = i + 1

PythonJava

from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n, m = len(nums1), len(nums2)
        # 确保 n <= m，缩短二分范围
        if n > m:
            return self.findMedianSortedArrays(nums2, nums1)

        l, r = 0, n
        while l <= r:
            i = (l + r) >> 1          # 切 nums1
            j = (m + n + 1) // 2 - i   # 切 nums2

            # 边界用 ±∞ 处理
            n1_lmax = nums1[i - 1] if i > 0 else -float('inf')
            n2_lmax = nums2[j - 1] if j > 0 else -float('inf')
            n1_rmin = nums1[i] if i < n else float('inf')
            n2_rmin = nums2[j] if j < m else float('inf')

            if n1_lmax <= n2_rmin and n2_lmax <= n1_rmin:
                if (m + n) % 2 == 0:
                    return (max(n1_lmax, n2_lmax) + min(n1_rmin, n2_rmin)) / 2
                else:
                    return max(n1_lmax, n2_lmax)
            elif n1_lmax > n2_rmin:
                r = i - 1   # i 太大，左移
            else:
                l = i + 1   # i 太小，右移

        return -1

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        // 确保 n <= m，缩短二分范围
        if (n > m) return findMedianSortedArrays(nums2, nums1);

        int l = 0, r = n;
        while (l <= r) {
            int i = (l + r) >>> 1;           // 切 nums1
            int j = (m + n + 1) / 2 - i;      // 切 nums2

            // 边界用 ±∞ 处理
            int n1_lmax = i > 0 ? nums1[i - 1] : Integer.MIN_VALUE;
            int n2_lmax = j > 0 ? nums2[j - 1] : Integer.MIN_VALUE;
            int n1_rmin = i < n ? nums1[i] : Integer.MAX_VALUE;
            int n2_rmin = j < m ? nums2[j] : Integer.MAX_VALUE;

            if (n1_lmax <= n2_rmin && n2_lmax <= n1_rmin) {
                if ((m + n) % 2 == 0) {
                    return (Math.max(n1_lmax, n2_lmax) + Math.min(n1_rmin, n2_rmin)) / 2.0;
                } else {
                    return Math.max(n1_lmax, n2_lmax);
                }
            } else if (n1_lmax > n2_rmin) {
                r = i - 1;   // i 太大，左移
            } else {
                l = i + 1;   // i 太小，右移
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度：O(log min(n, m)) — 对较短的数组二分
• 空间复杂度：O(1) — 只用了常数变量

LeetCode 20. 有效的括号

难度：⭐ 简单  |  标签：栈 字符串

🔗 LeetCode 原题链接

---

核心思路

遇左括号入栈，遇右括号弹出栈顶检查是否匹配。最后栈为空则全部匹配。

PythonJava

class Solution:
    def isValid(self, s: str) -> bool:
        stk = []
        lefts = {'(', '[', '{'}
        for c in s:
            if c in lefts:
                stk.append(c)
            else:
                if not stk:
                    return False
                top = stk.pop()
                if (c == ')' and top != '(') \
                        or (c == ']' and top != '[') \
                        or (c == '}' and top != '{'):
                    return False
        return not stk

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stk = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stk.push(c);
            } else {
                if (stk.isEmpty()) return false;
                char top = stk.pop();
                if ((c == ')' && top != '(')
                        || (c == ']' && top != '[')
                        || (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return stk.isEmpty();
    }
}

复杂度分析

• 时间复杂度：O(n) — 遍历一次
• 空间复杂度：O(n) — 栈最坏存 n/2 个左括号

LeetCode 155. 最小栈

难度：⭐⭐ 中等  |  标签：栈 设计

🔗 LeetCode 原题链接

---

核心思路

让每个节点同时记录入栈时的当前栈最小值，以空间换时间。

• push(x)：min_val = min(x, 栈顶.min_val)，新节点存 (x, min_val)
• getMin()：直接返回栈顶的 min_val
• 每次 pop 自动丢弃旧的最小值，不额外维护全局变量

PythonJava

class MinStack:

    class Node:
        def __init__(self, val: int, min_val: int):
            self.val = val
            self.min_val = min_val

    def __init__(self):
        self.stk = []

    def push(self, value: int) -> None:
        if not self.stk:
            self.stk.append(self.Node(value, value))
        else:
            self.stk.append(
                self.Node(value, min(value, self.stk[-1].min_val))
            )

    def pop(self) -> None:
        self.stk.pop()

    def top(self) -> int:
        return self.stk[-1].val

    def getMin(self) -> int:
        return self.stk[-1].min_val

class MinStack {
    private Deque<int[]> stk;

    public MinStack() {
        stk = new ArrayDeque<>();
    }

    public void push(int val) {
        if (stk.isEmpty()) {
            stk.push(new int[]{val, val});
        } else {
            stk.push(new int[]{val, Math.min(val, stk.peek()[1])});
        }
    }

    public void pop() {
        stk.pop();
    }

    public int top() {
        return stk.peek()[0];
    }

    public int getMin() {
        return stk.peek()[1];
    }
}

复杂度分析

• 时间复杂度：O(1) — 所有操作都是常数时间
• 空间复杂度：O(n) — 每个节点额外存一个 min_val

LeetCode 394. 字符串解码

难度：⭐⭐ 中等  |  标签：栈 递归 字符串

🔗 LeetCode 原题链接

---

核心思路

递归处理每个 k[ ... ] 结构，dfs() 返回解码后的子串。

• 遇到数字 → 解析完整数字 times → 跳过 [ → 递归 dfs() 取子串 → 跳过 ] → 重复 times 次
• 遇到字母 → 直接追加
• 遇到 ] 或字符串末尾 → 返回当前层结果

PythonJava

class Solution:
    def decodeString(self, s: str) -> str:
        n = len(s)
        u = 0

        def dfs() -> str:
            nonlocal u
            temp = ''
            while u < n and s[u] != ']':
                if s[u].isdigit():
                    times = 0
                    while u < n and s[u].isdigit():
                        times = times * 10 + int(s[u])
                        u += 1
                    u += 1  # 跳过 '['
                    sub = dfs()
                    u += 1  # 跳过 ']'
                    temp += times * sub
                else:
                    temp += s[u]
                    u += 1
            return temp

        return dfs()

class Solution {
    private int u = 0;

    public String decodeString(String s) {
        return dfs(s.toCharArray());
    }

    private String dfs(char[] cs) {
        StringBuilder sb = new StringBuilder();
        while (u < cs.length && cs[u] != ']') {
            if (Character.isDigit(cs[u])) {
                int times = 0;
                while (u < cs.length && Character.isDigit(cs[u])) {
                    times = times * 10 + (cs[u] - '0');
                    u++;
                }
                u++;  // 跳过 '['
                String sub = dfs(cs);
                u++;  // 跳过 ']'
                sb.append(sub.repeat(times));
            } else {
                sb.append(cs[u]);
                u++;
            }
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个字符处理一次
• 空间复杂度：O(n) — 递归栈深度 + 结果字符串

LeetCode 739. 每日温度

难度：⭐⭐ 中等  |  标签：栈 单调栈 数组

🔗 LeetCode 原题链接

---

核心思路

维护一个单调递减栈（从栈底到栈顶温度递减），从右往左遍历，栈中存下标。

• 当前温度 ≥ 栈顶温度 → 栈顶不可能是答案，弹出
• 栈非空 → 栈顶下标 - 当前下标 = 等待天数
• 栈空 → 之后不再有更高的温度，ans[i] = 0
• 最后将当前下标入栈

PythonJava

from typing import List


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stk, ans = [], [0] * n

        for i in range(n - 1, -1, -1):
            while stk and temperatures[i] >= temperatures[stk[-1]]:
                stk.pop()
            ans[i] = stk[-1] - i if stk else 0
            stk.append(i)

        return ans

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        Deque<Integer> stk = new ArrayDeque<>();
        int[] ans = new int[n];

        for (int i = n - 1; i >= 0; i--) {
            while (!stk.isEmpty()
                    && temperatures[i] >= temperatures[stk.peek()]) {
                stk.pop();
            }
            ans[i] = stk.isEmpty() ? 0 : stk.peek() - i;
            stk.push(i);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个元素入栈出栈各一次
• 空间复杂度：O(n) — 栈最多存 n 个下标

LeetCode 84. 柱状图中最大的矩形

难度：⭐⭐⭐ 困难  |  标签：栈 单调栈 数组

🔗 LeetCode 原题链接

---

核心思路

枚举每个柱子作为矩形的高度，该柱子能形成的最大矩形 = 高度 × (右边界 - 左边界 - 1)，其中左右边界是左右第一个比它矮的柱子。

用单调递增栈找左右边界，加哨兵简化代码：

• 在 heights 首尾各补一个 0（哨兵），保证栈不会为空，且所有柱子都能被弹出
• 遍历时，如果当前高度 ≤ 栈顶高度，说明栈顶的右边界到了，弹出计算面积
• 被弹出柱子的左边界 = 新栈顶（即栈中前一个元素），右边界 = 当前下标 i

PythonJava

from typing import List


class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 首尾加哨兵，避免空栈和最后残留
        heights = [0] + heights + [0]
        n = len(heights)
        stk, ans = [], 0

        for i in range(n):
            while stk and heights[stk[-1]] > heights[i]:
                h = heights[stk.pop()]       # 当前柱子的高度
                w = i - stk[-1] - 1          # 左右边界 = 当前 i - 新栈顶 - 1
                ans = max(ans, h * w)
            stk.append(i)

        return ans

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 首尾加哨兵，避免空栈和最后残留
        int n = heights.length;
        int[] h = new int[n + 2];
        System.arraycopy(heights, 0, h, 1, n);
        h[0] = h[n + 1] = 0;
        n += 2;

        Deque<Integer> stk = new ArrayDeque<>();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            while (!stk.isEmpty() && h[stk.peek()] > h[i]) {
                int height = h[stk.pop()];
                int width = i - stk.peek() - 1;
                ans = Math.max(ans, height * width);
            }
            stk.push(i);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n) — 每个元素入栈出栈各一次
• 空间复杂度：O(n) — 单调栈