算法刷题记录——LeetCode篇(3) [第201~300题](持续更新)

(优先整理热门100及面试150，不定期持续更新，欢迎关注)

---

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a_i, b_i] ，表示如果要学习课程 a_i 则 必须 先学习课程 b_i 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true

解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false

解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对互不相同

方法一：拓扑排序（BFS）

• 核心思想：通过入度表逐层消除无依赖的节点，若最终所有节点都被消除则无环。
• 步骤：
  1. 构建邻接表和入度表。
  2. 将入度为0的节点入队，依次处理并减少其后继节点的入度。
  3. 若处理节点数等于总节点数，则无环。

代码实现(Java)：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表和入度表
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            int ai = p[0], bi = p[1];
            adj.get(bi).add(ai); // 添加边 bi → ai
            inDegree[ai]++;      // ai 的入度增加
        }
      
        // 初始化队列，入度为0的课程入队
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
      
        // 处理队列中的课程
        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            for (int next : adj.get(course)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return count == numCourses;
    }
}

方法二：DFS检测环

• 核心思想：通过递归遍历节点，若在递归路径中遇到正在访问的节点，说明存在环。
• 步骤：
  1. 构建邻接表。
  2. 对每个未访问节点进行DFS，通过状态标记检测环。

代码实现(Java)：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建邻接表
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            int ai = p[0], bi = p[1];
            adj.get(bi).add(ai); // 添加边 bi → ai
        }
      
        // 访问状态：0-未访问，1-访问中，2-已访问
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (!dfs(adj, visited, i)) {
                    return false;
                }
            }
        }
        return true;
    }
  
    private boolean dfs(List<List<Integer>> adj, int[] visited, int node) {
        if (visited[node] == 1) return false; // 发现环
        if (visited[node] == 2) return true;   // 已处理过
        visited[node] = 1; // 标记为访问中
        for (int neighbor : adj.get(node)) {
            if (!dfs(adj, visited, neighbor)) {
                return false;
            }
        }
        visited[node] = 2; // 标记为已访问
        return true;
    }
}

复杂度分析

1. 拓扑排序（BFS）：时间复杂度O(V + E)，适用于大多数场景，尤其适合检测有向无环图（DAG）。
2. DFS检测环：时间复杂度O(V + E)，可能因递归深度导致栈溢出，适用于较小规模的图。

对比总结

方法	优点	缺点	适用场景
拓扑排序	无递归栈溢出风险	需要额外存储入度表	大规模图或稳定性要求高
DFS检测环	代码简洁，无需额外空间	递归深度可能受限	小规模图或代码简洁需求

---

208. 实现 Trie (前缀树)

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：

Trie();
// 初始化前缀树对象。
void insert(String word);
// 向前缀树中插入字符串 word 。
boolean search(String word);
// 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix);
//如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入:
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

输出:
[null, null, true, false, true, null, true]

解释：

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数总计不超过 3*10^4 次

实现方法

Trie（前缀树）是一种树形数据结构，用于高效存储和检索字符串。每个节点包含子节点数组（对应26个小写字母）和一个结束标志。插入时逐层创建节点，结束时标记；搜索时检查路径存在且结束标志为真；前缀匹配只需路径存在。

1. 节点结构：TrieNode类包含一个长度为26的子节点数组和一个结束标记isEnd。
2. 初始化：构造时创建根节点。
3. 插入：遍历单词字符，逐层创建子节点，结尾设置isEnd。
4. 搜索：检查路径存在且结尾isEnd为真。
5. 前缀检查：只需路径存在，不检查结束标记。

代码实现(Java)：

class Trie {
    private class TrieNode {
        TrieNode[] children;
        boolean isEnd;

        TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }

    private TrieNode root;

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

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

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                return null;
            }
            current = current.children[index];
        }
        return current;
    }
}

复杂度分析

• 时间复杂度
  • 插入：O(L)，L为单词长度；
  • 搜索/前缀：O(L)，L为查询字符串长度。
• 空间复杂度：O(N×L)，N为插入单词数，L为平均长度。

---

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

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

方法：三向切分快速选择法

利用快速选择算法结合三向切分，高效定位第K大元素。

1. 三向切分：

   • 将数组分为三个区域：大于基准值、等于基准值、小于基准值；
   • 采用类似荷兰国旗问题的分区方式，一次遍历完成分类；

2. 递归选择：

   • 根据当前分区后的元素数量分布，决定递归处理方向；
   • 大于区域元素足够时递归处理前部；
   • 数量不足但包含等于区域时直接返回基准值；
   • 否则递归处理后部并调整k值；

随机选择基准值避免最坏情况，每次递归至少排除一个区域元素。

代码实现(Java)：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k);
    }
  
    private int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
      
        Random rand = new Random();
        int pivotIndex = left + rand.nextInt(right - left + 1);
        int pivot = nums[pivotIndex];
      
        // 三向切分（荷兰国旗问题）
        int low = left;
        int high = right;
        int mid = left;
      
        while (mid <= high) {
            if (nums[mid] > pivot) {  // 大于pivot的交换到前部
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] < pivot) { // 小于pivot的交换到后部
                swap(nums, mid, high);
                high--;
            } else {  // 等于时继续后移
                mid++;
            }
        }
      
        // 计算各区域元素数量
        int gtCount = low - left;       // 大于pivot的数目
        int eqCount = high - low + 1;   // 等于pivot的数目
      
        if (k <= gtCount) {             // 目标在大于区域
            return quickSelect(nums, left, low - 1, k);
        } else if (k <= gtCount + eqCount) { // 目标在等于区域
            return pivot;
        } else {                        // 目标在小于区域
            return quickSelect(nums, high + 1, right, k - gtCount - eqCount);
        }
    }
  
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析

平均时间复杂度 O(n)，最坏情况 O(n^2)。

---

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目范围在 [0, 100] 内
• -100 <= Node.val <= 100

方法一：递归法

递归交换每个节点的左右子树，自顶向下逐层翻转。

代码实现(Java)：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // 交换当前节点的左右子节点
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 递归处理左右子树
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

方法二：广度优先搜索（BFS）

利用队列层序遍历，逐个节点交换左右子树。

代码实现(Java)：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 交换左右子节点
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            // 将子节点加入队列继续处理
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        return root;
    }
}

方法三：深度优先搜索（DFS）迭代法

使用栈模拟递归过程，前序遍历时交换左右子树。

代码实现(Java)：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            // 交换左右子节点
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            // 将子节点压入栈（先右后左保证处理顺序）
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return root;
    }
}

复杂度分析

1. 递归法：从根节点开始，交换左右子节点，然后递归处理左右子树。每个节点只需处理一次，时间复杂度为 (O(n))，空间复杂度为 (O(h))（树的高度）。
2. BFS迭代：借助队列层序遍历，每次处理节点时交换其左右子节点，并将子节点加入队列。时间复杂度 (O(n))，空间复杂度 (O(n))（最坏情况）。
3. DFS迭代：使用栈实现深度优先遍历，处理节点时交换左右子节点。时间复杂度 (O(n))，空间复杂度 (O(h))（树的高度）。

---

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

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

树中的节点数为 n 。

• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

方法一：递归中序遍历（提前终止）

• 利用中序遍历左-根-右的顺序天然有序的特点。
• 遍历时对访问的节点计数，当计数达到k时记录结果并立即终止递归（通过返回值true提前退出递归栈）。
• 剪枝优化，左子树找到目标后直接返回，避免无意义的右子树遍历。

代码实现(Java)：

class Solution {
    private int count;
    private int result;

    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inorder(root);
        return result;
    }

    private boolean inorder(TreeNode node) {
        if (node == null) return false;
        if (inorder(node.left)) return true;  // 左子树已找到目标
        if (--count == 0) {                   // 处理当前节点
            result = node.val;
            return true;                      // 找到目标，终止递归
        }
        return inorder(node.right);           // 继续遍历右子树
    }
}

方法二：迭代中序遍历（显式栈）

• 用栈显式保存遍历路径，先深度优先遍历到最左节点。
• 每次弹出栈顶元素时计数，找到第k个元素时直接返回。
• 栈的深度为树高，避免递归栈溢出的风险。

代码实现(Java)：

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        int count = 0;
      
        while (curr != null || !stack.isEmpty()) {
            // 遍历到最左节点
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            // 回溯处理节点
            curr = stack.pop();
            if (++count == k) return curr.val; // 找到第k小的元素
            curr = curr.right;                // 转向右子树
        }
        return -1; // 题目保证k有效，此处不会执行
    }
}

复杂度分析

• 时间复杂度：两种方法均为 O(k)，最坏情况为 O(n)（当k=n时需要遍历整棵树）。
• 空间复杂度：递归法 O(h)（h为树高），迭代法 O(h)（显式栈的空间占用）。

---

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3

解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5

解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

• 树中节点数目在范围 [2, 1e5] 内
• -10^9 <= Node.val <= 10^9
• 所有 Node.val 互不相同
• p != q
• p 和 q 均存在于给定的二叉树中

方法一：递归法（后序遍历）

• 核心思想：利用二叉树的后序遍历特性，自底向上查找公共祖先。
• 关键点：
  • 当某节点左右子树分别包含p和q时，该节点即为LCA。
  • 若仅单侧子树包含目标节点，则返回该侧结果。

代码实现(Java)：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 当前节点为null或等于p/q时直接返回
        if (root == null || root == p || root == q) return root;
      
        // 递归处理左右子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
      
        // 情况1：左右子树均包含目标节点，当前节点为LCA
        if (left != null && right != null) return root;
      
        // 情况2：仅一侧有目标节点，返回该侧结果
        return left != null ? left : right;
    }
}

方法二：迭代法（父指针回溯）

• 核心思想：通过层序遍历建立父节点映射，回溯祖先链求交点。
• 关键步骤：
  • 使用队列进行层序遍历，记录每个节点的父节点。
  • 回溯p的路径存入集合，再回溯q的路径寻找交点。

代码实现(Java)：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 存储所有节点的父指针
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        parent.put(root, null);
        queue.add(root);
      
        // 层序遍历建立父指针映射
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                parent.put(node.left, node);
                queue.add(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                queue.add(node.right);
            }
        }
      
        // 回溯p的祖先链
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
      
        // 查找q的祖先链中第一个公共节点
        while (!ancestors.contains(q)) {
            q = parent.get(q);
        }
        return q;
    }
}

复杂度分析

1. 递归法（后序遍历）：

   • 时间复杂度：O(n)，每个节点访问一次。
   • 空间复杂度：O(h)，递归栈深度（h为树高）。

2. 迭代法（父指针回溯）：

   • 时间复杂度：O(n)，两次线性扫描。
   • 空间复杂度：O(n)，存储父指针和祖先集合。

对比总结

方法	优点	缺点	适用场景
递归法	代码简洁，空间效率高	递归深度较大时可能栈溢出	树结构较平衡的情况
迭代法	避免递归栈溢出	需要额外存储父节点	树结构深或需要路径操作

---

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

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在32 位整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 输入保证数组 answer[i] 在32 位整数范围内

进阶：
你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为 额外空间。）

方法：前后缀乘积优化

1. 前缀乘积：从左到右遍历数组，计算每个元素左侧所有元素的乘积，存入结果数组。
2. 后缀乘积动态计算：从右到左遍历数组，用变量动态维护右侧乘积，并乘到结果数组中，实现原地更新。

代码实现(Java)：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
      
        // 计算左侧乘积
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }
      
        // 计算右侧乘积并相乘
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= right;
            right *= nums[i];
        }
      
        return answer;
    }
}

复杂度分析

• 时间复杂度：O(n)，两次遍历数组。
• 空间复杂度：O(1)（输出数组不计入额外空间），仅使用常数变量 right。

---

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

解释：

滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

方法一：双端队列

使用双端队列维护一个单调递减队列，存储可能成为窗口最大值的元素索引。遍历数组时，维护队列的单调性，并确保队列中的元素在窗口范围内。队列头部始终是当前窗口的最大值。

代码实现(Java)：

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || k <= 0) return new int[0];
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            // 移除超出窗口范围的元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            // 维护单调递减特性
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            // 记录窗口最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}

复杂度分析：

• 时间复杂度：O(n)，每个元素最多入队和出队一次。
• 空间复杂度：O(k)，队列最多存储 k 个元素。

方法二：大根堆（优先队列）

使用大根堆存储元素值和索引。每次滑动窗口时，将新元素加入堆中，并移除堆顶不在当前窗口范围内的元素。堆顶元素即为当前窗口的最大值。

代码实现(Java)：

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
      
        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{nums[i], i});
            // 移除窗口外的最大值
            while (!pq.isEmpty() && pq.peek()[1] <= i - k) {
                pq.poll();
            }
            // 记录结果
            if (i >= k - 1) {
                result[i - k + 1] = pq.peek()[0];
            }
        }
        return result;
    }
}

复杂度分析：

• 时间复杂度：O(n log k)，堆操作的时间复杂度为 O(log k)。
• 空间复杂度：O(n)，堆最多存储 n 个元素。

方法三：分块预处理

将数组分成大小为k的块，预处理每个块的前缀最大值和后缀最大值。对于每个窗口，最大值可以通过组合相邻块的后缀和前缀最大值得到。

代码实现(Java)：

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];
      
        // 计算前缀最大值
        for (int i = 0; i < n; i++) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            } else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }
      
        // 计算后缀最大值
        for (int i = n - 1; i >= 0; i--) {
            if (i == n - 1 || (i + 1) % k == 0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }
      
        // 生成结果
        int[] result = new int[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            int j = i + k - 1;
            result[i] = Math.max(suffixMax[i], prefixMax[j]);
        }
        return result;
    }
}

复杂度分析：

• 时间复杂度：O(n)，预处理和结果生成各需要O(n)时间。
• 空间复杂度：O(n)，存储前缀和后缀最大值数组。

对比总结

1. 双端队列：通过维护单调队列实现高效的最大值获取，是本题最优解。
2. 大根堆：逻辑简单，但在极端情况下性能较差。
3. 分块预处理：通过预处理块的最大值，实现线性时间复杂度，适合对空间不敏感的场景。

---

279. 完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。
完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3

解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2

解释：13 = 4 + 9

提示：

• 1 <= n <= 10^4

方法一：动态规划

通过构建 dp 数组，其中 dp[i] 表示组成整数 i 所需的最少完全平方数的数量。利用动态规划逐步填充 dp 数组，最终得到 dp[n] 的值。

1. 初始化：dp[0] = 0（基础情况），其他位置初始化为最大值（如 Integer.MAX_VALUE）。
2. 状态转移：对于每个数 i，遍历所有可能的平方数 j*j，更新 dp[i] = min(dp[i], dp[i - j*j] + 1)。
3. 遍历顺序：外层遍历目标值 i，内层遍历可能的平方数 j。

代码实现(Java)：

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0; // 初始条件
      
        // 遍历每个整数i，计算其最少平方数个数
        for (int i = 1; i <= n; i++) {
            // 遍历所有可能的平方数j*j（j*j <= i）
            for (int j = 1; j * j <= i; j++) {
                // 更新dp[i]为最小值
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}

方法二：四平方和定理(数学解法)

四平方和定理 (Lagrange’s four-square theorem) 说明每个正整数均可表示为4个整数的平方和。其中，当且仅当该数满足4^k*(8m+7)时只能表示为四平方和，其他形式都可以表示为三平方和。

1. 检查是否为完全平方数：如果是，直接返回1。
2. 检查是否满足形式4^k*(8m +7)：若是，返回4。
3. 检查是否能表示为两个平方数之和：若是，返回2。
4. 其他情况返回3：根据定理，剩余情况只需3个平方数。

代码实现(Java)：

class Solution {
    public int numSquares(int n) {
        // 判断是否为完全平方数
        if (isPerfectSquare(n)) {
            return 1;
        }
        // 检查是否满足4^k*(8m +7)的条件
        int num = n;
        while (num % 4 == 0) {
            num /= 4;
        }
        if (num % 8 == 7) {
            return 4;
        }
        // 检查是否可以表示为两个平方数的和
        for (int i = 1; i * i <= n; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }
        // 其他情况返回3
        return 3;
    }
  
    // 辅助函数，判断x是否为完全平方数
    private boolean isPerfectSquare(int x) {
        int s = (int) Math.sqrt(x);
        return s * s == x;
    }
}

复杂度分析

• 方法一时间复杂度：外层循环：O(n)，内层循环：O(√i)，总复杂度：O(n√n)。
• 方法二时间复杂度：O(√n)

---

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

MedianFinder();
// 初始化 MedianFinder 对象。
void addNum(int num);
// 将数据流中的整数 num 添加到数据结构中。
double findMedian();
// 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入:
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]

输出:
[null, null, null, 1.5, null, 2.0]

解释：

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示：

• -10^5 <= num <= 10^5
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 5 * 10^4 次调用 addNum 和 findMedian

方法：双堆法

使用两个堆（大顶堆和小顶堆）分别存储数据流的较小和较大半部分，实现中位数的快速查询。

1. 数据结构设计：

   • 大顶堆存储较小半部分元素，堆顶为最大元素
   • 小顶堆存储较大半部分元素，堆顶为最小元素
   • 始终维持大顶堆元素数 ≥ 小顶堆元素数

2. 添加元素流程：

   1. 新元素先加入大顶堆
   2. 将大顶堆的最大值传递给小顶堆
   3. 若小顶堆元素更多，返还最小值到大顶堆

3. 中位数计算：

   • 当元素总数为奇数时，直接返回大顶堆堆顶
   • 当元素总数为偶数时，返回两堆顶平均值

代码实现(Java)：

class MedianFinder {
    private PriorityQueue<Integer> maxHeap; // 存储较小的一半（大顶堆）
    private PriorityQueue<Integer> minHeap; // 存储较大的一半（小顶堆）

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }
  
    public void addNum(int num) {
        // 1. 先加入大顶堆并传递最大值到小顶堆
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());
      
        // 2. 平衡堆大小，保证大顶堆不小于小顶堆
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
  
    public double findMedian() {
        // 根据堆大小差异返回中位数
        return maxHeap.size() > minHeap.size() 
               ? maxHeap.peek() 
               : (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

复杂度分析

• 时间复杂度：
  • addNum(): O(log n) 堆插入和删除操作
  • findMedian(): O(1) 直接访问堆顶
• 空间复杂度：O(n) 存储所有元素

---

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4

解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

进阶：
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

方法一：动态规划

使用动态规划数组 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。对于每个元素，遍历其之前的所有元素，若当前元素更大，则更新 dp[i]。

代码实现(Java)：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

方法二：贪心 + 二分查找

维护一个 tails 数组，tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素。通过二分查找快速定位插入或替换位置。

代码实现(Java)：

class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int num : nums) {
            int left = 0, right = tails.size();
            // 二分查找第一个 >= num 的位置
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails.get(mid) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if (left == tails.size()) {
                tails.add(num);
            } else {
                tails.set(left, num);
            }
        }
        return tails.size();
    }
}

复杂度分析

方法	时间复杂度	空间复杂度	适用场景
动态规划	O(n²)	O(n)	简单直观，小规模数据
二分+贪心	O(n log n)	O(n)	大规模数据，效率要求高

---

博客源文件Gitee仓库:

gitee.com/richardmilos/allen-csdn-notes

(持续更新，未完待续)