1. 六道题为什么值得反复做从刷完到刷透的分水岭面试算法题这个东西很多人刷了几百道真到面试现场还是卡壳。问题不在于题量而在于有没有把一类题做透。我前后带过几个准备校招的朋友也自己复盘过不少次面试经历发现一个规律真正拉开差距的不是谁刷的题多而是谁能把一组有代表性的题吃干榨净从每道题里抽出可迁移的思维模型。这次拿到的六道题来源是常见的面试题库平台覆盖了链表、二叉树、动态规划、双指针、栈与队列这几大高频板块。它们看起来是六道独立的题但如果你只把它们当成六个孤立的练习做完就忘那基本等于白做。我的做法是把六道题当成一个最小完备集每道题都追问三个问题——这道题考的是什么底层能力它的暴力解和最优解差在哪里如果面试官把条件改一改我还能不能接住这篇文章就是围绕这三个问题展开的。我会逐题拆解思路、给出可运行的代码、标注容易踩的坑更重要的是分享我在实际做题和面试中总结出来的迁移套路。适合正在准备技术面试的在校生、想跳槽的开发者也适合单纯想把算法基本功重新捡起来的人。哪怕你现在连链表和数组的区别都说不利索跟着走一遍也能有收获因为我会把每一步的为什么讲清楚而不是甩一段代码让你自己悟。先说一个总的原则面试算法题考的不是你会不会写代码而是你能不能在有限时间内把一个模糊问题拆成清晰的步骤并且用代码准确表达出来。所以刷题时最忌讳的就是看一眼题解哦原来是这样下一道。正确的姿势是先自己想卡住了记录卡在哪再看题解然后合上题解自己重写一遍最后隔两天再默写一遍。这六道题我就是按这个流程过的下面逐一说。2. 链表类题目的通用拆解框架2.1 链表题为什么总在指针上翻车链表题是面试里的常客因为它特别能暴露一个人对指针操作的理解深度。数组你可以靠下标随便访问链表不行你只能顺着 next 指针一格一格走。很多人写链表题翻车根本原因就一个在移动指针之前没有先把下一步需要的信息保存下来。举个最常见的场景——反转链表。新手容易写成这样让当前节点的 next 指向前一个节点然后想移动到下一个节点结果发现下一个节点已经找不到了因为它的指针刚被你改掉了。这就是典型的顺序错误。正确的做法是三步走先存下一个节点再改当前节点的指向最后移动前驱和当前指针。这个先存后改再移的口诀几乎能套用到所有链表指针操作题上。我在实际做题时养成了一个习惯每写一行涉及指针赋值的代码就在脑子里画一遍当前链表的状态。画不了就说明你没想清楚。这个习惯帮我避开了至少一半的链表 bug。2.2 反转链表的迭代与递归两套写法反转链表这道题迭代和递归两种写法都得会因为面试官经常追问你能用递归再写一遍吗。迭代版本的核心就是三个指针prev前驱、curr当前、next暂存。初始时 prev 为空curr 指向头节点。循环体里先把 curr.next 存到 next再把 curr.next 指向 prev然后 prev 移到 currcurr 移到 next。循环结束时 curr 为空prev 就是新的头节点。def reverse_list(head): prev None curr head while curr: next_node curr.next # 先存 curr.next prev # 再改 prev curr # 后移 curr next_node return prev递归版本稍微绕一点但理解了就很简单。递归的思路是假设从第二个节点开始往后的部分已经反转好了我只需要把第二个节点的 next 指向头节点头节点的 next 指向空然后返回新的头节点。def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_head这里有个坑head.next None这行千万别漏。漏了的话原来的头节点和第二个节点之间会形成环整个链表就废了。我见过不少人递归写对了大半就栽在这一行上。2.3 快慢指针链表题的万能钥匙除了反转链表题里另一个高频套路是快慢指针。判断链表有没有环、找链表中点、找倒数第 k 个节点全靠它。判断有环的逻辑很直观快指针每次走两步慢指针每次走一步。如果链表有环快指针一定会在环里追上慢指针如果没环快指针会先走到空。这个追上的直觉很好理解——就像两个人在环形跑道上跑步跑得快的人迟早会从后面追上慢的人。找中点也是同理快指针走到头的时候慢指针刚好在中间。这里有个细节要注意当节点数是偶数时快慢指针的初始化方式决定了慢指针最终停在前半段的最后一个还是后半段的第一个。这个差异在做重排链表这类题时非常关键写之前一定要想清楚你要的是哪个。提示快慢指针的初始化常见有两种——都从头节点出发或者快指针先走一步。选哪种取决于题目要求的中点是偏左还是偏右别死记画个四节点和五节点的链表自己推一遍就明白了。3. 二叉树遍历递归思维与迭代实现的取舍3.1 前中后序遍历的递归本质二叉树是算法面试的另一座大山。前序、中序、后序遍历递归写法几乎是本能反应因为它们的定义本身就是递归的前序是根左右中序是左根右后序是左右根。你只要把访问根节点的位置换一下三行代码就能切换三种遍历。def inorder(root): if not root: return inorder(root.left) # 左 print(root.val) # 根 inorder(root.right) # 右递归写法的好处是简洁、不易出错坏处是当树很深时会爆栈。所以面试官经常会追问能用迭代写吗这时候就考验你对递归本质上是栈这句话的理解了。3.2 用显式栈模拟递归调用迭代实现遍历核心是用一个栈来模拟系统调用栈。前序遍历最简单先把根压栈然后循环弹出节点、访问、再把右孩子和左孩子依次压栈注意顺序因为栈是后进先出想先访问左孩子就得后压左孩子。中序遍历稍微难一点因为要先一路走到最左边。思路是用一个指针从根开始只要指针不为空就压栈并往左走指针为空了就弹出栈顶访问然后转向右孩子。def inorder_iterative(root): stack [] curr root while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() print(curr.val) curr curr.right后序遍历的迭代是最绕的因为它要求左右根而栈天然适合处理根左右。有个取巧的办法按根右左的顺序遍历最后把结果反转就得到左右根了。这个技巧我第一次见的时候觉得挺妙后来发现面试里用出来面试官往往会点头。3.3 层序遍历与BFS的边界处理层序遍历用的是队列而不是栈属于广度优先搜索BFS。它的经典写法是每轮循环先记录当前队列的长度这个长度就是当前层的节点数然后一次性处理完这一层的所有节点把它们的左右孩子入队。from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result这里的关键是level_size len(queue)这一行。如果你不记录这个长度直接while queue里逐个处理就没法区分哪些节点属于同一层。这个分层的技巧在二叉树的最大宽度锯齿形层序遍历等题里都会用到值得单独记一下。注意层序遍历里判断左右孩子是否存在再入队比入队后再判断空要清晰。虽然两种写法都对但前者能少一次循环内的空判断代码也更易读。4. 动态规划从暴力递归到状态转移的进化路径4.1 动态规划到底在规划什么动态规划DP是很多人面试时的噩梦因为它不像链表、二叉树那样有直观的图形可以画。但其实 DP 的核心思想非常朴素如果一个问题的解可以由它的子问题的解推导出来并且这些子问题会被重复计算那就把子问题的解存起来避免重复劳动。理解 DP 最好的路径是三步走先写出暴力递归再发现重叠子问题最后用记忆化或递推消除重复计算。跳过第一步直接看状态转移方程是很多人学不会 DP 的根本原因——你连暴力解都没想清楚怎么可能直接写出优化解4.2 爬楼梯与斐波那契DP的入门模型爬楼梯是最经典的 DP 入门题每次可以爬 1 阶或 2 阶问爬到第 n 阶有多少种方法。暴力递归的思路是到达第 n 阶要么从第 n-1 阶爬 1 阶上来要么从第 n-2 阶爬 2 阶上来所以f(n) f(n-1) f(n-2)。但直接递归会重复计算大量子问题时间复杂度是指数级的。用记忆化自顶向下或者递推自底向上就能降到 O(n)。def climb_stairs(n): if n 2: return n prev, curr 1, 2 for _ in range(3, n 1): prev, curr curr, prev curr return curr这里用两个变量滚动更新把空间复杂度压到了 O(1)。这个滚动数组的技巧在 DP 里非常常用只要状态转移只依赖前几个状态就能用有限变量代替整个数组。4.3 状态定义与转移方程DP的两大命门DP 题难难在两件事状态怎么定义转移方程怎么写。状态定义决定了你的 dp 数组每个位置代表什么含义转移方程决定了这些位置之间怎么推导。以最长递增子序列为例。状态定义是dp[i]表示以第 i 个元素结尾的最长递增子序列长度。转移方程是对于每个 i遍历它前面所有的 j如果nums[j] nums[i]那么dp[i] max(dp[i], dp[j] 1)。最后答案是 dp 数组里的最大值而不是 dp[n-1]因为最长递增子序列不一定以最后一个元素结尾。def length_of_lis(nums): if not nums: return 0 dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这个 O(n²) 的解法面试里够用了但如果面试官要求优化到 O(n log n)就得用贪心 二分查找的思路维护一个递增的辅助数组。这个进阶解法我建议先理解 O(n²) 版本再去看优化否则容易两头都记不牢。提示写 DP 时先确定答案对应 dp 数组的哪个位置。很多题答案是 dp[n-1]但像最长递增子序列、最大子数组和这类题答案是整个 dp 数组的最值。这个细节错了代码逻辑再对也拿不到分。5. 双指针与滑动窗口把O(n²)降到O(n)的实战套路5.1 双指针的两种形态对撞与同向双指针是性价比极高的技巧因为它往往能把 O(n²) 的暴力解优化到 O(n)。它有两种典型形态对撞指针一个从头、一个从尾向中间靠拢和同向指针两个指针都从头出发一快一慢。对撞指针的经典应用是两数之和有序数组和盛最多水的容器。以两数之和为例数组有序的前提下左指针指向最小值右指针指向最大值如果两数之和小于目标左指针右移大于目标右指针左移。这样每次移动都能排除掉一整行或一整列的可能性所以是 O(n)。同向指针的经典应用是删除有序数组中的重复项和移动零。核心思路是用一个慢指针维护已处理好的区域快指针负责扫描。快指针遇到符合条件的元素就把它放到慢指针的位置慢指针前进。5.2 滑动窗口处理子串子数组问题的利器滑动窗口本质上是同向双指针的一种特化专门用来处理连续子数组/子串的问题。它的模板非常固定右指针不断扩张窗口当窗口不满足条件时左指针收缩窗口过程中记录答案。以无重复字符的最长子串为例。右指针向右扩展把字符加入窗口如果遇到重复字符左指针就向右移动直到窗口内不再有重复。用一个哈希集合记录窗口内的字符就能在 O(1) 时间内判断重复。def length_of_longest_substring(s): char_set set() left 0 max_len 0 for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left 1 char_set.add(s[right]) max_len max(max_len, right - left 1) return max_len这个模板的通用性极强把判断窗口是否合法和更新答案这两处换掉就能解一大类题。我建议把这个模板背下来面试时能省不少思考时间。5.3 窗口收缩时机的判断逻辑滑动窗口最容易出错的地方是什么时候收缩左指针。有的题要求窗口恰好满足某条件有的题要求不满足就收缩这两种逻辑写起来差别很大。我的经验是先明确窗口的合法状态是什么。对于最长类问题通常是窗口不合法时收缩对于最短类问题通常是窗口合法时收缩并记录答案。这个区分想清楚了代码结构就清晰了。注意滑动窗口里right - left 1是窗口长度这个 1 千万别漏。我见过太多人因为漏了这个 1答案永远差一位debug 半天才发现。6. 栈与队列看似简单却暗藏玄机的数据结构6.1 用栈实现队列与用队列实现栈用两个栈实现队列和用两个队列实现栈是考察对这两种数据结构本质理解的经典题。栈是后进先出队列是先进先出要用一种模拟另一种核心在于倒腾数据。用两个栈实现队列一个入栈push 时用一个出栈pop 时用。入队时直接压入入栈出队时如果出栈为空就把入栈的所有元素依次弹出并压入出栈这样顺序就反过来了再从出栈弹出即可。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x): self.in_stack.append(x) def pop(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop()这个倒腾操作有个关键性质每个元素最多被倒腾一次所以均摊时间复杂度是 O(1)。面试时如果被问到时间复杂度一定要说均摊而不是简单说 O(1) 或 O(n)这个细节能体现你的严谨。6.2 单调栈下一个更大元素的通用解法单调栈是栈的一个高级应用专门解决下一个更大/更小元素这类问题。它的核心是维护一个单调递增或递减的栈当新元素破坏单调性时就弹出栈顶并记录答案。以每日温度为例给定一个温度数组求每一天要等多少天才能遇到更高的温度。用单调递减栈栈里存的是下标。遍历温度数组当当前温度大于栈顶下标对应的温度时说明栈顶那天找到了下一个更高温度弹出并计算天数差。def daily_temperatures(temperatures): n len(temperatures) answer [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: prev stack.pop() answer[prev] i - prev stack.append(i) return answer单调栈的难点在于想清楚栈里存什么、什么时候弹。我的经验是栈里存下标而不是值因为很多时候需要计算距离弹出时机就是找到了答案的时机。把这两点想清楚单调栈的题基本都能套。6.3 有效括号栈的入门必修课有效括号是栈最基础的应用但基础不代表简单。它的逻辑是遇到左括号就压栈遇到右括号就看栈顶是不是对应的左括号是就弹出不是或栈空就返回 false。遍历结束后栈必须为空。def is_valid(s): mapping {): (, ]: [, }: {} stack [] for char in s: if char in mapping: top stack.pop() if stack else # if mapping[char] ! top: return False else: stack.append(char) return not stack这里用了一个小技巧用一个字典把右括号映射到对应的左括号这样判断逻辑就统一了不用写一堆 if-else。另外stack.pop() if stack else #这个写法处理了栈空的情况用一个不可能匹配的字符占位避免额外的边界判断。提示有效括号的变体很多比如最长有效括号删除最少括号使字符串有效。这些变体的基础都是这道题把基础打牢变体就是加一层逻辑的事。7. 六道题背后的通用能力地图把这六道题拆完你会发现它们其实在考同一批底层能力只是换了不同的外衣。题目类型核心考察能力可迁移的思维模型链表反转指针操作的顺序意识先存后改再移二叉树遍历递归与迭代的转换用栈/队列模拟调用栈动态规划状态定义与转移推导暴力递归到记忆化再到递推双指针/滑动窗口排除法的边界控制用单调性排除不可能解栈与队列数据结构的本质理解用辅助结构倒腾顺序单调栈维护单调性的时机判断弹出即找到答案这张表是我自己复盘时整理的它帮我意识到面试算法题的数量是无限的但底层思维模型是有限的。与其盲目刷题不如把每个模型吃透遇到新题时先判断它属于哪个模型再套用对应的套路。我在实际面试中还有一个体会面试官更看重你的思考过程而不是最终代码。所以做题时一定要边写边说把你的思路、你的犹豫、你的取舍都表达出来。哪怕最后代码没写完只要思路清晰面试官也会给不错的评价。反过来闷头写完代码但讲不清楚为什么这么写反而容易被扣分。最后分享一个我自己的练习方法每做完一道题合上题解用一句话总结这道题的核心套路是什么然后把它归类到上面那张表里。坚持一段时间你会发现自己看到新题时脑子里会自动跳出这题是滑动窗口或者这题得用单调栈这种条件反射就是刷题刷到位了的标志。 
长河君 · 2026/10/16 23:22:53 · 阅读 1.2k 面试算法六道题精讲：从链表到动态规划的通用解题套路
1. 六道题为什么值得反复做从刷完到刷透的分水岭面试算法题这个东西很多人刷了几百道真到面试现场还是卡壳。问题不在于题量而在于有没有把一类题做透。我前后带过几个准备校招的朋友也自己复盘过不少次面试经历发现一个规律真正拉开差距的不是谁刷的题多而是谁能把一组有代表性的题吃干榨净从每道题里抽出可迁移的思维模型。这次拿到的六道题来源是常见的面试题库平台覆盖了链表、二叉树、动态规划、双指针、栈与队列这几大高频板块。它们看起来是六道独立的题但如果你只把它们当成六个孤立的练习做完就忘那基本等于白做。我的做法是把六道题当成一个最小完备集每道题都追问三个问题——这道题考的是什么底层能力它的暴力解和最优解差在哪里如果面试官把条件改一改我还能不能接住这篇文章就是围绕这三个问题展开的。我会逐题拆解思路、给出可运行的代码、标注容易踩的坑更重要的是分享我在实际做题和面试中总结出来的迁移套路。适合正在准备技术面试的在校生、想跳槽的开发者也适合单纯想把算法基本功重新捡起来的人。哪怕你现在连链表和数组的区别都说不利索跟着走一遍也能有收获因为我会把每一步的为什么讲清楚而不是甩一段代码让你自己悟。先说一个总的原则面试算法题考的不是你会不会写代码而是你能不能在有限时间内把一个模糊问题拆成清晰的步骤并且用代码准确表达出来。所以刷题时最忌讳的就是看一眼题解哦原来是这样下一道。正确的姿势是先自己想卡住了记录卡在哪再看题解然后合上题解自己重写一遍最后隔两天再默写一遍。这六道题我就是按这个流程过的下面逐一说。2. 链表类题目的通用拆解框架2.1 链表题为什么总在指针上翻车链表题是面试里的常客因为它特别能暴露一个人对指针操作的理解深度。数组你可以靠下标随便访问链表不行你只能顺着 next 指针一格一格走。很多人写链表题翻车根本原因就一个在移动指针之前没有先把下一步需要的信息保存下来。举个最常见的场景——反转链表。新手容易写成这样让当前节点的 next 指向前一个节点然后想移动到下一个节点结果发现下一个节点已经找不到了因为它的指针刚被你改掉了。这就是典型的顺序错误。正确的做法是三步走先存下一个节点再改当前节点的指向最后移动前驱和当前指针。这个先存后改再移的口诀几乎能套用到所有链表指针操作题上。我在实际做题时养成了一个习惯每写一行涉及指针赋值的代码就在脑子里画一遍当前链表的状态。画不了就说明你没想清楚。这个习惯帮我避开了至少一半的链表 bug。2.2 反转链表的迭代与递归两套写法反转链表这道题迭代和递归两种写法都得会因为面试官经常追问你能用递归再写一遍吗。迭代版本的核心就是三个指针prev前驱、curr当前、next暂存。初始时 prev 为空curr 指向头节点。循环体里先把 curr.next 存到 next再把 curr.next 指向 prev然后 prev 移到 currcurr 移到 next。循环结束时 curr 为空prev 就是新的头节点。def reverse_list(head): prev None curr head while curr: next_node curr.next # 先存 curr.next prev # 再改 prev curr # 后移 curr next_node return prev递归版本稍微绕一点但理解了就很简单。递归的思路是假设从第二个节点开始往后的部分已经反转好了我只需要把第二个节点的 next 指向头节点头节点的 next 指向空然后返回新的头节点。def reverse_list_recursive(head): if not head or not head.next: return head new_head reverse_list_recursive(head.next) head.next.next head head.next None return new_head这里有个坑head.next None这行千万别漏。漏了的话原来的头节点和第二个节点之间会形成环整个链表就废了。我见过不少人递归写对了大半就栽在这一行上。2.3 快慢指针链表题的万能钥匙除了反转链表题里另一个高频套路是快慢指针。判断链表有没有环、找链表中点、找倒数第 k 个节点全靠它。判断有环的逻辑很直观快指针每次走两步慢指针每次走一步。如果链表有环快指针一定会在环里追上慢指针如果没环快指针会先走到空。这个追上的直觉很好理解——就像两个人在环形跑道上跑步跑得快的人迟早会从后面追上慢的人。找中点也是同理快指针走到头的时候慢指针刚好在中间。这里有个细节要注意当节点数是偶数时快慢指针的初始化方式决定了慢指针最终停在前半段的最后一个还是后半段的第一个。这个差异在做重排链表这类题时非常关键写之前一定要想清楚你要的是哪个。提示快慢指针的初始化常见有两种——都从头节点出发或者快指针先走一步。选哪种取决于题目要求的中点是偏左还是偏右别死记画个四节点和五节点的链表自己推一遍就明白了。3. 二叉树遍历递归思维与迭代实现的取舍3.1 前中后序遍历的递归本质二叉树是算法面试的另一座大山。前序、中序、后序遍历递归写法几乎是本能反应因为它们的定义本身就是递归的前序是根左右中序是左根右后序是左右根。你只要把访问根节点的位置换一下三行代码就能切换三种遍历。def inorder(root): if not root: return inorder(root.left) # 左 print(root.val) # 根 inorder(root.right) # 右递归写法的好处是简洁、不易出错坏处是当树很深时会爆栈。所以面试官经常会追问能用迭代写吗这时候就考验你对递归本质上是栈这句话的理解了。3.2 用显式栈模拟递归调用迭代实现遍历核心是用一个栈来模拟系统调用栈。前序遍历最简单先把根压栈然后循环弹出节点、访问、再把右孩子和左孩子依次压栈注意顺序因为栈是后进先出想先访问左孩子就得后压左孩子。中序遍历稍微难一点因为要先一路走到最左边。思路是用一个指针从根开始只要指针不为空就压栈并往左走指针为空了就弹出栈顶访问然后转向右孩子。def inorder_iterative(root): stack [] curr root while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() print(curr.val) curr curr.right后序遍历的迭代是最绕的因为它要求左右根而栈天然适合处理根左右。有个取巧的办法按根右左的顺序遍历最后把结果反转就得到左右根了。这个技巧我第一次见的时候觉得挺妙后来发现面试里用出来面试官往往会点头。3.3 层序遍历与BFS的边界处理层序遍历用的是队列而不是栈属于广度优先搜索BFS。它的经典写法是每轮循环先记录当前队列的长度这个长度就是当前层的节点数然后一次性处理完这一层的所有节点把它们的左右孩子入队。from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result这里的关键是level_size len(queue)这一行。如果你不记录这个长度直接while queue里逐个处理就没法区分哪些节点属于同一层。这个分层的技巧在二叉树的最大宽度锯齿形层序遍历等题里都会用到值得单独记一下。注意层序遍历里判断左右孩子是否存在再入队比入队后再判断空要清晰。虽然两种写法都对但前者能少一次循环内的空判断代码也更易读。4. 动态规划从暴力递归到状态转移的进化路径4.1 动态规划到底在规划什么动态规划DP是很多人面试时的噩梦因为它不像链表、二叉树那样有直观的图形可以画。但其实 DP 的核心思想非常朴素如果一个问题的解可以由它的子问题的解推导出来并且这些子问题会被重复计算那就把子问题的解存起来避免重复劳动。理解 DP 最好的路径是三步走先写出暴力递归再发现重叠子问题最后用记忆化或递推消除重复计算。跳过第一步直接看状态转移方程是很多人学不会 DP 的根本原因——你连暴力解都没想清楚怎么可能直接写出优化解4.2 爬楼梯与斐波那契DP的入门模型爬楼梯是最经典的 DP 入门题每次可以爬 1 阶或 2 阶问爬到第 n 阶有多少种方法。暴力递归的思路是到达第 n 阶要么从第 n-1 阶爬 1 阶上来要么从第 n-2 阶爬 2 阶上来所以f(n) f(n-1) f(n-2)。但直接递归会重复计算大量子问题时间复杂度是指数级的。用记忆化自顶向下或者递推自底向上就能降到 O(n)。def climb_stairs(n): if n 2: return n prev, curr 1, 2 for _ in range(3, n 1): prev, curr curr, prev curr return curr这里用两个变量滚动更新把空间复杂度压到了 O(1)。这个滚动数组的技巧在 DP 里非常常用只要状态转移只依赖前几个状态就能用有限变量代替整个数组。4.3 状态定义与转移方程DP的两大命门DP 题难难在两件事状态怎么定义转移方程怎么写。状态定义决定了你的 dp 数组每个位置代表什么含义转移方程决定了这些位置之间怎么推导。以最长递增子序列为例。状态定义是dp[i]表示以第 i 个元素结尾的最长递增子序列长度。转移方程是对于每个 i遍历它前面所有的 j如果nums[j] nums[i]那么dp[i] max(dp[i], dp[j] 1)。最后答案是 dp 数组里的最大值而不是 dp[n-1]因为最长递增子序列不一定以最后一个元素结尾。def length_of_lis(nums): if not nums: return 0 dp [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这个 O(n²) 的解法面试里够用了但如果面试官要求优化到 O(n log n)就得用贪心 二分查找的思路维护一个递增的辅助数组。这个进阶解法我建议先理解 O(n²) 版本再去看优化否则容易两头都记不牢。提示写 DP 时先确定答案对应 dp 数组的哪个位置。很多题答案是 dp[n-1]但像最长递增子序列、最大子数组和这类题答案是整个 dp 数组的最值。这个细节错了代码逻辑再对也拿不到分。5. 双指针与滑动窗口把O(n²)降到O(n)的实战套路5.1 双指针的两种形态对撞与同向双指针是性价比极高的技巧因为它往往能把 O(n²) 的暴力解优化到 O(n)。它有两种典型形态对撞指针一个从头、一个从尾向中间靠拢和同向指针两个指针都从头出发一快一慢。对撞指针的经典应用是两数之和有序数组和盛最多水的容器。以两数之和为例数组有序的前提下左指针指向最小值右指针指向最大值如果两数之和小于目标左指针右移大于目标右指针左移。这样每次移动都能排除掉一整行或一整列的可能性所以是 O(n)。同向指针的经典应用是删除有序数组中的重复项和移动零。核心思路是用一个慢指针维护已处理好的区域快指针负责扫描。快指针遇到符合条件的元素就把它放到慢指针的位置慢指针前进。5.2 滑动窗口处理子串子数组问题的利器滑动窗口本质上是同向双指针的一种特化专门用来处理连续子数组/子串的问题。它的模板非常固定右指针不断扩张窗口当窗口不满足条件时左指针收缩窗口过程中记录答案。以无重复字符的最长子串为例。右指针向右扩展把字符加入窗口如果遇到重复字符左指针就向右移动直到窗口内不再有重复。用一个哈希集合记录窗口内的字符就能在 O(1) 时间内判断重复。def length_of_longest_substring(s): char_set set() left 0 max_len 0 for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left 1 char_set.add(s[right]) max_len max(max_len, right - left 1) return max_len这个模板的通用性极强把判断窗口是否合法和更新答案这两处换掉就能解一大类题。我建议把这个模板背下来面试时能省不少思考时间。5.3 窗口收缩时机的判断逻辑滑动窗口最容易出错的地方是什么时候收缩左指针。有的题要求窗口恰好满足某条件有的题要求不满足就收缩这两种逻辑写起来差别很大。我的经验是先明确窗口的合法状态是什么。对于最长类问题通常是窗口不合法时收缩对于最短类问题通常是窗口合法时收缩并记录答案。这个区分想清楚了代码结构就清晰了。注意滑动窗口里right - left 1是窗口长度这个 1 千万别漏。我见过太多人因为漏了这个 1答案永远差一位debug 半天才发现。6. 栈与队列看似简单却暗藏玄机的数据结构6.1 用栈实现队列与用队列实现栈用两个栈实现队列和用两个队列实现栈是考察对这两种数据结构本质理解的经典题。栈是后进先出队列是先进先出要用一种模拟另一种核心在于倒腾数据。用两个栈实现队列一个入栈push 时用一个出栈pop 时用。入队时直接压入入栈出队时如果出栈为空就把入栈的所有元素依次弹出并压入出栈这样顺序就反过来了再从出栈弹出即可。class MyQueue: def __init__(self): self.in_stack [] self.out_stack [] def push(self, x): self.in_stack.append(x) def pop(self): if not self.out_stack: while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop()这个倒腾操作有个关键性质每个元素最多被倒腾一次所以均摊时间复杂度是 O(1)。面试时如果被问到时间复杂度一定要说均摊而不是简单说 O(1) 或 O(n)这个细节能体现你的严谨。6.2 单调栈下一个更大元素的通用解法单调栈是栈的一个高级应用专门解决下一个更大/更小元素这类问题。它的核心是维护一个单调递增或递减的栈当新元素破坏单调性时就弹出栈顶并记录答案。以每日温度为例给定一个温度数组求每一天要等多少天才能遇到更高的温度。用单调递减栈栈里存的是下标。遍历温度数组当当前温度大于栈顶下标对应的温度时说明栈顶那天找到了下一个更高温度弹出并计算天数差。def daily_temperatures(temperatures): n len(temperatures) answer [0] * n stack [] for i in range(n): while stack and temperatures[i] temperatures[stack[-1]]: prev stack.pop() answer[prev] i - prev stack.append(i) return answer单调栈的难点在于想清楚栈里存什么、什么时候弹。我的经验是栈里存下标而不是值因为很多时候需要计算距离弹出时机就是找到了答案的时机。把这两点想清楚单调栈的题基本都能套。6.3 有效括号栈的入门必修课有效括号是栈最基础的应用但基础不代表简单。它的逻辑是遇到左括号就压栈遇到右括号就看栈顶是不是对应的左括号是就弹出不是或栈空就返回 false。遍历结束后栈必须为空。def is_valid(s): mapping {): (, ]: [, }: {} stack [] for char in s: if char in mapping: top stack.pop() if stack else # if mapping[char] ! top: return False else: stack.append(char) return not stack这里用了一个小技巧用一个字典把右括号映射到对应的左括号这样判断逻辑就统一了不用写一堆 if-else。另外stack.pop() if stack else #这个写法处理了栈空的情况用一个不可能匹配的字符占位避免额外的边界判断。提示有效括号的变体很多比如最长有效括号删除最少括号使字符串有效。这些变体的基础都是这道题把基础打牢变体就是加一层逻辑的事。7. 六道题背后的通用能力地图把这六道题拆完你会发现它们其实在考同一批底层能力只是换了不同的外衣。题目类型核心考察能力可迁移的思维模型链表反转指针操作的顺序意识先存后改再移二叉树遍历递归与迭代的转换用栈/队列模拟调用栈动态规划状态定义与转移推导暴力递归到记忆化再到递推双指针/滑动窗口排除法的边界控制用单调性排除不可能解栈与队列数据结构的本质理解用辅助结构倒腾顺序单调栈维护单调性的时机判断弹出即找到答案这张表是我自己复盘时整理的它帮我意识到面试算法题的数量是无限的但底层思维模型是有限的。与其盲目刷题不如把每个模型吃透遇到新题时先判断它属于哪个模型再套用对应的套路。我在实际面试中还有一个体会面试官更看重你的思考过程而不是最终代码。所以做题时一定要边写边说把你的思路、你的犹豫、你的取舍都表达出来。哪怕最后代码没写完只要思路清晰面试官也会给不错的评价。反过来闷头写完代码但讲不清楚为什么这么写反而容易被扣分。最后分享一个我自己的练习方法每做完一道题合上题解用一句话总结这道题的核心套路是什么然后把它归类到上面那张表里。坚持一段时间你会发现自己看到新题时脑子里会自动跳出这题是滑动窗口或者这题得用单调栈这种条件反射就是刷题刷到位了的标志。