【Leetcode】随笔

文章目录

• • 题目一：最小栈（LeetCode 155，困难）
  • • 题目分析
    • 解题思路
    • 示例代码
    • 代码解析
  • 题目二：二叉树中的最大路径和（LeetCode 124，困难）
  • • 题目分析
    • 解题思路
    • 示例代码
    • 代码解析
  • 题目三：N 皇后（LeetCode 51，困难）
  • • 题目分析
    • 解题思路
    • 示例代码
    • 代码解析

🌈你好呀！我是 山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨

题目一：最小栈（LeetCode 155，困难）

题目分析

设计一个支持 push、pop、top 操作，并能在常数时间内检索到最小元素的栈。需要实现 MinStack 类：

• MinStack() 初始化堆栈对象；
• void push(int val) 将元素 val 推入堆栈；
• void pop() 删除堆栈顶部的元素；
• int top() 获取堆栈顶部的元素；
• int getMin() 获取堆栈中的最小元素。

例如：输入操作序列为 [\"MinStack\",\"push\",\"push\",\"push\",\"getMin\",\"pop\",\"top\",\"getMin\"]，参数为 [[],[-2],[0],[-3],[],[],[],[]]，输出为 [null,null,null,null,-3,null,0,-2]（push 三次后最小元素为 -3，pop 后栈顶为 0，此时最小元素为 -2）。

解题思路

采用双栈设计，核心是用“数据栈”存储正常的栈元素，用“辅助栈”同步维护当前栈中的最小元素，确保 getMin() 操作能在 O(1) 时间完成。具体设计逻辑如下：

1. 双栈定义：
   • data_stack：数据栈，存储所有推入的元素，负责 push、pop、top 操作的基础实现；
   • min_stack：辅助栈，存储对应 data_stack 状态下的最小元素，栈顶始终是当前 data_stack 中的最小元素。
2. 关键操作逻辑：
   • push 操作：
     1. 将元素 val 推入 data_stack；
     2. 若 min_stack 为空，或 val ≤ min_stack[-1]（当前元素小于等于辅助栈顶元素），则将 val 推入 min_stack（确保辅助栈顶始终是最小值，相等时也推入是为了处理重复元素的 pop 逻辑）。
   • pop 操作：
     1. 从 data_stack 弹出栈顶元素 top_val；
     2. 若 top_val == min_stack[-1]（弹出的元素是当前最小值），则同步从 min_stack 弹出栈顶元素（确保辅助栈与数据栈状态一致）。
   • top 操作：直接返回 data_stack[-1]（数据栈顶元素）。
   • getMin 操作：直接返回 min_stack[-1]（辅助栈顶元素，即当前最小值）。

示例代码

class MinStack: def __init__(self): # 数据栈：存储所有元素 self.data_stack = [] # 辅助栈：存储对应数据栈状态下的最小元素，栈顶为当前最小值 self.min_stack = [] def push(self, val: int) -> None: # 数据栈正常推入元素 self.data_stack.append(val) # 辅助栈：空或当前元素≤栈顶时推入（确保栈顶是最小值） if not self.min_stack or val <= self.min_stack[-1]: self.min_stack.append(val) def pop(self) -> None: # 数据栈弹出栈顶元素 top_val = self.data_stack.pop() # 若弹出的是当前最小值，辅助栈同步弹出 if top_val == self.min_stack[-1]: self.min_stack.pop() def top(self) -> int: # 返回数据栈顶元素 return self.data_stack[-1] def getMin(self) -> int: # 返回辅助栈顶元素（当前最小值） return self.min_stack[-1]# 测试示例minStack = MinStack()minStack.push(-2)minStack.push(0)minStack.push(-3)print(\"当前最小值1：\", minStack.getMin()) # 输出：-3minStack.pop()print(\"当前栈顶：\", minStack.top()) # 输出：0print(\"当前最小值2：\", minStack.getMin()) # 输出：-2

代码解析

• 辅助栈的设计关键：push 时“小于等于”才推入，而非“小于”，是为了处理重复最小值的情况。例如 data_stack 推入 [-2, -2]，min_stack 同步推入 [-2, -2]，当第一次 pop 时，min_stack 弹出一个 -2，栈顶仍为 -2，确保 getMin() 结果正确。
• 时间复杂度：所有操作（push、pop、top、getMin）均为 O(1)，满足题目“常数时间检索最小元素”的要求。
• 空间复杂度：O(n)（n 为栈中元素个数），辅助栈最多存储 n 个元素（当元素严格递减时），属于合理的空间开销，换取时间效率的优化。

题目二：二叉树中的最大路径和（LeetCode 124，困难）

题目分析

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。路径和是路径中各节点值的总和。给你一个二叉树的根节点 root，返回其最大路径和。例如：输入根节点为 [1,2,3]（根节点 1，左子节点 2，右子节点 3），输出 6（路径为 2→1→3，和为 2+1+3=6）；输入根节点为 [-10,9,20,null,null,15,7]，输出 42（路径为 15→20→7，和为 15+20+7=42）。

解题思路

采用后序遍历（递归），核心是定义“以当前节点为起点，向下延伸的最大路径和”，通过递归计算每个节点的左右子树贡献，再结合当前节点值更新全局最大路径和。具体逻辑如下：

1. 核心概念：
   • 节点贡献：以当前节点为起点，向下延伸到任意叶子节点的路径中，最大的路径和（路径只能向子节点延伸，不能同时包含左右子树，否则会形成“分叉路径”，无法作为其他路径的一部分）。
   • 全局最大路径和：可能包含两种情况：一是“以当前节点为中心，连接左右子树的路径和”（左右子树贡献 + 当前节点值）；二是递归过程中已记录的最大路径和，需不断比较更新。
2. 递归函数设计：
   • 函数 max_contribution(node)：返回以 node 为起点的最大贡献值（即向下延伸的最大路径和）。
   • 递归终止条件：若 node 为 null，返回 0（空节点贡献为 0）。
   • 递归计算：
     1. 计算左子树的最大贡献 left_contrib = max(max_contribution(node.left), 0)（若左子树贡献为负，取 0，相当于不选择左子树）；
     2. 计算右子树的最大贡献 right_contrib = max(max_contribution(node.right), 0)（同理，负贡献取 0）；
     3. 计算“以当前节点为中心的路径和” current_path_sum = node.val + left_contrib + right_contrib，更新全局最大路径和 max_sum（若 current_path_sum 更大）；
     4. 返回当前节点的最大贡献 node.val + max(left_contrib, right_contrib)（路径只能选左或右子树中的一条，不能同时选，否则会分叉）。
3. 初始化与执行：
   • 初始化全局变量 max_sum 为负无穷（处理树中所有节点值为负的情况）；
   • 调用递归函数 max_contribution(root)，触发后序遍历；
   • 递归结束后，max_sum 即为二叉树的最大路径和。

示例代码

# 二叉树节点定义class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def maxPathSum(self, root: TreeNode) -> int: # 全局变量：存储最大路径和（初始为负无穷，处理全负节点） self.max_sum = float(\'-inf\') def max_contribution(node): if not node: return 0 # 空节点贡献为0 # 计算左右子树的最大贡献，负贡献取0（不选该子树） left_contrib = max(max_contribution(node.left), 0) right_contrib = max(max_contribution(node.right), 0) # 计算以当前节点为中心的路径和，更新全局最大路径和 current_path_sum = node.val + left_contrib + right_contrib if current_path_sum > self.max_sum: self.max_sum = current_path_sum # 返回当前节点的最大贡献（只能选左或右子树中的一条路径） return node.val + max(left_contrib, right_contrib) # 触发递归，计算所有节点的贡献 max_contribution(root) return self.max_sum# 测试示例1：root = [1,2,3]root1 = TreeNode(1)root1.left = TreeNode(2)root1.right = TreeNode(3)print(\"最大路径和1：\", Solution().maxPathSum(root1)) # 输出：6# 测试示例2：root = [-10,9,20,null,null,15,7]root2 = TreeNode(-10)root2.left = TreeNode(9)root2.right = TreeNode(20)root2.right.left = TreeNode(15)root2.right.right = TreeNode(7)print(\"最大路径和2：\", Solution().maxPathSum(root2)) # 输出：42# 测试示例3：root = [-3]（单个负节点）root3 = TreeNode(-3)print(\"最大路径和3：\", Solution().maxPathSum(root3)) # 输出：-3

代码解析

• 负贡献处理：递归计算左右子树贡献时，用 max(contrib, 0) 过滤负贡献，相当于“不选择该子树”，避免负数值拉低路径和（例如节点值为 -5，左子树贡献为 -3，此时选择左子树会让路径和更小，故取 0，即不选左子树）。
• 路径和的两种场景：
  • “以当前节点为中心的路径”：包含左右子树，是一条完整的独立路径，需更新全局最大和；
  • “当前节点的贡献”：仅包含左或右子树，是后续父节点路径的一部分，需返回给父节点使用。
• 时间复杂度：O(n)（n 为二叉树节点数，每个节点仅被访问一次，后序遍历）；空间复杂度：O(h)（h 为二叉树高度，递归栈深度为 h，最坏情况为 O(n)，如斜树）。

题目三：N 皇后（LeetCode 51，困难）

题目分析

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。给你一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 \'Q\' 和 \'.\' 分别代表了皇后和空位。例如：输入 n=4，输出 2 种解决方案（具体方案见示例代码）；输入 n=1，输出 1 种解决方案（仅 [\"Q\"]）。

解题思路

采用回溯法，核心是通过“逐行放置皇后”，结合“列、左上右下斜线、右上左下斜线”的冲突检测，逐步探索所有合法的放置方案。具体逻辑如下：

1. 冲突检测关键：
   • 列冲突：若某一列已放置皇后，后续行不能在该列放置；
   • 斜线冲突：
     • 左上右下斜线（行号 - 列号 为固定值）：例如 (0,0)、(1,1)、(2,2) 属于同一斜线，行号-列号=0；
     • 右上左下斜线（行号 + 列号 为固定值）：例如 (0,2)、(1,1)、(2,0) 属于同一斜线，行号+列号=2。
   • 用三个集合分别记录“已使用的列”used_cols、“已使用的左上右下斜线”used_diag1（存储行-列）、“已使用的右上左下斜线”used_diag2（存储行+列），实现 O(1) 冲突检测。
2. 回溯函数设计：
   • 函数 backtrack(row, path)：row 表示当前要放置皇后的行，path 表示当前已确定的皇后位置（如 path[0]=1 表示第 0 行皇后在第 1 列）。
   • 终止条件：若 row == n（所有行已放置皇后），将 path 转换为对应的棋盘字符串（如 [1,3,0,2] 转换为 [\".Q..\", \"...Q\", \"Q...\", \"..Q.\"]），加入结果列表。
   • 回溯逻辑：
     1. 遍历当前行的每一列 col（0 ≤ col < n）；
     2. 计算当前位置的斜线标识 diag1 = row - col，diag2 = row + col；
     3. 若 col 在 used_cols，或 diag1 在 used_diag1，或 diag2 在 used_diag2（存在冲突），跳过该列；
     4. 若无冲突：
        • 将 col 加入 path，并将 col、diag1、diag2 分别加入对应集合；
        • 递归调用 backtrack(row + 1, path)（处理下一行）；
        • 回溯：从 path 和三个集合中移除当前 col、diag1、diag2（探索其他列的可能性）。
3. 初始化与执行：初始化结果列表 result，调用 backtrack(0, [])，最终返回 result。

示例代码

class Solution: def solveNQueens(self, n: int) -> list[list[str]]: result = [] # 存储所有解决方案 # 三个集合：记录已使用的列、左上右下斜线、右上左下斜线 used_cols = set() used_diag1 = set() # 行 - 列 used_diag2 = set() # 行 + 列 def backtrack(row, path): # 终止条件：所有行已放置皇后 if row == n: # 将path转换为棋盘字符串（如[1,3,0,2]→[\".Q..\", \"...Q\", \"Q...\", \"..Q.\"]） board = [] for col in path:  row_str = \'.\' * col + \'Q\' + \'.\' * (n - col - 1)  board.append(row_str) result.append(board) return # 遍历当前行的每一列 for col in range(n): diag1 = row - col diag2 = row + col # 冲突检测：列或斜线已被使用 if col in used_cols or diag1 in used_diag1 or diag2 in used_diag2:  continue # 选择当前列：加入path和集合 path.append(col) used_cols.add(col) used_diag1.add(diag1) used_diag2.add(diag2) # 递归处理下一行 backtrack(row + 1, path) # 回溯：撤销选择 path.pop() used_cols.remove(col) used_diag1.remove(diag1) used_diag2.remove(diag2) # 从第0行开始回溯，初始path为空 backtrack(0, []) return result# 测试示例n1 =4solution = Solution()queens_solutions1 = solution.solveNQueens(n1)print(f\"n={n1}时的解决方案数：{len(queens_solutions1)}\")print(\"n=4的解决方案：\")for idx, sol in enumerate(queens_solutions1, 1): print(f\"方案{idx}：\") for row in sol: print(row) print()n2 = 1queens_solutions2 = solution.solveNQueens(n2)print(f\"n={n2}时的解决方案数：{len(queens_solutions2)}\")print(\"n=1的解决方案：\")for sol in queens_solutions2: for row in sol: print(row)

代码解析

• 冲突检测的高效性：通过三个集合记录已使用的列和斜线，避免了每次检测时遍历已放置的皇后（传统暴力检测为 O(row) 时间），将冲突检测优化为 O(1)，大幅提升回溯效率。
• 回溯的核心逻辑：“选择→递归→撤销选择”三步闭环，确保探索所有可能的放置方案。例如在第 0 行选择列 1 后，递归处理第 1 行，探索无冲突的列；若后续行无法放置皇后，会回溯到第 0 行，尝试其他列（如列 3）。
• 棋盘转换的细节：path 存储每一行皇后的列索引（如 [1,3,0,2]），转换为棋盘字符串时，通过 \'.\' * col + \'Q\' + \'.\' * (n - col - 1) 生成每行的字符串，直观反映皇后位置。
• 时间复杂度：O(n!)（n 皇后问题的解空间复杂度为 n!，回溯过程需遍历所有可能的合法放置，无法进一步优化）；空间复杂度：O(n)（path 长度为 n，三个集合最多存储 n 个元素，递归栈深度为 n）。

✨ 本次分享的3道题覆盖了“数据结构设计（最小栈）”“二叉树递归（最大路径和）”“回溯搜索（N皇后）”三大高频题型，这类题目不仅需要掌握核心算法思想，还需注重边界处理和效率优化。如果对某类题型的细节（如回溯剪枝技巧）或其他困难题有进一步需求，随时告诉我哦！😊
🏠 更多算法解析和实战技巧，欢迎到我的CSDN主页交流：山顶风景独好😍