吴师兄算法心法

双指针的本质，是用两个一前一后（或一快一慢）的指针，把本来要两层循环干的事压成一层。它有四个常见长相，认清了就不会乱：

对撞指针：数组有序时，一头一尾往中间夹。和大了就缩右、小了就进左——两数之和 II、盛水容器都是它。
快慢指针：一个走两步、一个走一步。在链表里找中点、判环；在数组里做原地去重。
滑动窗口：右指针扩、左指针缩，维护一段「连续区间」满足某条件，求最长 / 最短。
读写分离：一个指针负责读、一个负责写，原地移除 / 搬运元素。

# 对撞：有序数组里找一对
l, r = 0, n - 1
while l < r:
    if 满足(l, r): return ...
    elif 偏大: r -= 1        # 缩右变小
    else: l += 1            # 进左变大

我常跟学生说：看到「有序 + 找一对」，手就该先把 l、r 摆上去；看到「链表中点 / 判环」，脑子里先冒出 slow、fast。这种条件反射，就是熟练。

DP 之所以难，是因为它「抽象」。但只要每次都老老实实问自己这五个问题，再难的 DP 也能拆开：

① 状态是什么——dp[i] 到底代表什么？（如「以 i 结尾的最长…」「前 i 个能否…」）
② 怎么转移——dp[i] 由哪些更小的状态推来？这是核心，也是动画最该看清的一步。
③ 边界——最小的子问题答案是多少（dp[0]、空串、单个元素）。
④ 遍历顺序——0-1 背包内层倒着、完全背包内层正着，方向错了答案就错。
⑤ 能不能压空间——只依赖前一两项时，用滚动变量把二维压成一维。

# 选 / 不选：一类一维 DP 的通用骨架
prev2, prev1 = 0, 0
for x in nums:
    cur = max(prev1,            # 不选当前
              prev2 + x)        # 选当前（接更前面的）
    prev2, prev1 = prev1, cur

很多人卡在「想不出转移方程」。我的笨办法是：先别想公式，先用动画把一个小例子的表格一格一格填出来，填着填着，方程自己就浮出来了。这也是我把每道 DP 都做成填表动画的原因。

回溯说穿了就是在一棵「决策树」上做深度优先搜索：进入一个分支前做选择，退出来时把选择撤销，换下一个分支再试。三件套永远是这三步：

path.append(选项)        # ① 选
backtrack(下一步)        # ② 递归
path.pop()              # ③ 撤销

剩下的区别只在两个旋钮：用 start 还是 used——组合 / 子集用 start 索引去重（只往后选），排列用 used 数组标记谁用过；能不能复用——递归传 i 表示同一个数能再选，传 i+1 表示用过就不能再用。再加上「剩余目标 < 0 就剪枝」，组合总和这类带和的题也拿下了。

一个最容易翻车的细节：收集结果时一定要存 path[:] 这个副本，直接存 path 会被后面的回溯改掉。这个坑我见过太多人踩。

二叉树几乎所有题都长一个样：递归到空节点返回一个基准值，否则先拿到左、右子树的答案，再合并成当前节点的答案。换的只是「合并」这一步：

def dfs(node):
    if not node: return 基准值      # 空节点的答案
    L = dfs(node.left)
    R = dfs(node.right)
    return 合并(L, R, node)         # 拼成当前节点的答案

求深度，合并就是 1 + max(L, R)；求节点数就是 1 + L + R。还有一类更妙的——返回值给父亲、全局变量记答案：算直径、最大路径和时，递归返回「能向上延伸的深度」，同时用一个全局量记下「横跨当前节点的路径」。把这两者分清，是树形题不出错的关键。

至于遍历，前 / 中 / 后序根本不用单独记——就是同一个递归骨架，把「处理当前节点」那行代码放在递归左、右之间的不同位置而已。

二分查找人人会写，但真正用好它的人不多。两个进阶认知能让你打开新世界：

① 大多数二分题，本质是「找第一个满足某条件的位置」（下界二分）。把模板写成左闭右开，满足就收右、不满足就进左，最后返回 l，边界问题一次理清。
② 不一定要在数组里二分——只要「答案越大越满足（或越不满足）」具有单调性，就能直接在答案的取值范围上二分。求最小速度、x 的平方根、能否在 D 天送达，都是这个套路。

# 下界二分：找第一个满足 cond 的位置
l, r = 0, n
while l < r:
    m = (l + r) // 2
    if cond(m): r = m       # 满足，答案在 m 或更左
    else: l = m + 1
return l

写二分老是差一、死循环？记死一套模板，别每次现想边界。我自己十年只用这一个左闭右开模板，再没出过错。

遇到「嵌套结构」和「需要回头看最近一个」的问题，栈就是天选之子。它有两个高频面孔：

配对 / 嵌套：括号匹配、表达式求值、路径化简——进入一层就压栈、退出一层就弹栈合并。栈顶永远是「离我最近、还没处理完」的那个。
单调栈：求「下一个更大 / 更小的元素」的利器。维护一个单调的栈，新元素打破单调性时就弹栈结算。每日温度、接雨水都靠它把 O(n²) 降到 O(n)。

# 单调栈：为每个元素找右边第一个更大的
stack = []                   # 存还没找到答案的下标
for i, x in enumerate(arr):
    while stack and x > arr[stack[-1]]:
        j = stack.pop(); ans[j] = i - j   # 结算 j
    stack.append(i)

单调栈最反直觉的一点：栈里存的是下标不是值。因为你往往需要「位置差」来算答案。这点想通了，单调栈就不神秘了。

这六套心法，覆盖了八九成的面试题。把它们当成积木，难题往往就是几块积木的拼装——比如回文链表 = 找中点 + 反转 + 双指针比较。

⛳ 按学习路径开始练 →