LeetCode 1340 这道题我印象特别深。当时打开题目页面心里还想着不过是跳一跳而已结果从读题到第一版代码通过硬是耗了 97 分钟。事后复盘这 97 分钟大半都浪费在跳跃条件的翻译上——题面只说了能跳到哪些位置没说清哪些位置会挡住视线而挡板这件事想明白了整道题就成功了一半。这篇文章我会记录完整的思考链路先讲为什么暴力记忆化能过这道题再讲怎么用单调栈预处理配合排序 DP 把复杂度从 O(n·d) 压到 O(n log n)最后把我当初踩过的递归深度、等号、同高度等细节一并列出来。无论你是刚开始刷困难题还是想在面试里把这个题的优化版本讲清楚这篇都能给你一个能直接落地的参考。1. 跳跃游戏 V 的可见性规则挡板才是真正的难点1.1 题目到底在说什么题目给你一个整数数组arr和一个最大跳跃距离d。你可以从任意下标出发每次跳跃只能朝左或者朝右一个方向且距离不能超过d。从下标i能跳到下标j的条件有两个arr[j] arr[i]目标位置必须严格更矮i和j之间所有下标对应的高度也都必须严格小于arr[i]。注意第二点是很多人第一次读题会漏掉的不是只看目标点矮不矮中间任何一根柱子如果比你当前站的位置更高或一样高你的视线就被挡住了后面再远的位置统统不可达。我习惯用柱子的类比来记你站在一根高度为H的柱子上往左或往右看只要遇到一根高度大于等于H的柱子视线就断了。在视线断掉之前你能看到的所有严格矮于H的柱子才是你这一步能跳过去的地方。这个可见性模型和后面要讲的单调栈优化是一一对应的理解它比背代码重要得多。1.2 为什么它是困难题难点不在 DP 公式而在建模坦白说这题的 DP 状态定义非常简单dp[i]表示从i出发最多能访问多少个下标转移就是dp[i] 1 max(dp[j])其中j满足上面的跳跃条件。真正让它配得上困难的有三个点第一个难点是依赖顺序不按数组下标走。普通一维 DP 通常从左往右或者从右往左扫一遍就行但这题的转移只发生在严格更矮的两个点之间可能从左边跳到右边也可能从右边跳到左边你没法用一个固定方向的下标遍历保证依赖全部就绪。第二个难点是贪心陷阱。有人会想从当前位置出发每次在可见范围内挑最高的柱子跳这样走得最远。这个直觉是错的——最高的那根柱子很可能是个死胡同反而选一根中等高度的柱子后面能串起更多点。我在初期也在这个方向上浪费了不少时间最后发现这题本质是 DAG 上的最长路径不是贪心。第三个难点就是可见性区间。可跳的位置不是一个简单的值域条件而是被第一个挡住你的柱子切成两个连续区间。这个区间性质恰恰是优化到 O(n log n) 的钥匙。1.3 一个能完全手算的样例为了后面讲解方便我设计一个小样例你可以自己用手推一遍验证感觉。arr [5, 1, 4, 2]d 2。逐个看每个下标的跳跃范围下标 3高度 2左右都被更高的柱子挡死左边是 4不可跳dp[3] 1下标 1高度 1左边 5 挡右边 4 挡不可跳dp[1] 1下标 2高度 4左边能看到下标 1高度 1再往左的下标 0 高度 5 把自己挡住右边能看到下标 3高度 2所以dp[2] 1 max(dp[1], dp[3]) 2下标 0高度 5右边能看到下标 1高度 1和下标 2高度 4中间下标 1 高度 1 小于 5距离分别 1 和 2 都不超过d下标 3 距离 3 超出限制所以dp[0] 1 max(dp[1], dp[2]) 3。最终答案是max(dp) 3对应路径0 - 2 - 1或0 - 2 - 3。这个样例虽然小但已经包含了距离截断视线阻挡向两边跳三个关键要素后面所有代码我都会用它来校验。2. 第一版暴力记忆化把最多能到哪翻译成状态转移2.1 自顶向下的 DFS 模型先别急着上优化我把第一版能过的思路完整说一遍这是所有高级做法的地基。定义dfs(i)从下标i出发最多能访问多少个下标包含起点自己。那么转移就是dfs(i) 1 max(dfs(j))其中j是所有满足跳跃条件的位置。如果根本没有可跳的位置dfs(i)就是 1。这个递归天然是自顶向下的从当前点出发递归去看它能跳到的所有点再由那些点的结果推出自己的结果。为什么这个递归不需要显式的 visited 数组因为跳跃路径的高度是严格递减的arr[i] arr[j] arr[k] ...。你从高往下走永远不可能绕回一个曾经访问过的更高的点。所以状态图是一个 DAG不存在环。这也是为什么这题的路径问题可以放心交给 DP 而不是图搜索去处理。2.2 两个等价写法for break 和 while 条件短路最直观的写法是用 for 循环向左、向右扫描遇到第一个高度大于等于当前高度的位置就 break。from functools import lru_cache import sys sys.setrecursionlimit(10 ** 6) class Solution: def maxJumps(self, arr: List[int], d: int) - int: n len(arr) lru_cache(None) def dfs(i: int) - int: best 1 # 向左探索 j i - 1 while j 0 and i - j d: if arr[j] arr[i]: break best max(best, dfs(j) 1) j - 1 # 向右探索 j i 1 while j n and j - i d: if arr[j] arr[i]: break best max(best, dfs(j) 1) j 1 return best ans 0 for i in range(n): ans max(ans, dfs(i)) return ans还有一个更简洁的写法把距离条件和高度条件合并进 while 条件lru_cache(None) def dfs(i: int) - int: best 1 j i - 1 while j 0 and i - j d and arr[j] arr[i]: best max(best, dfs(j) 1) j - 1 j i 1 while j n and j - i d and arr[j] arr[i]: best max(best, dfs(j) 1) j 1 return best这两个写法行为完全一致。第二个写法里arr[j] arr[i]一旦不成立整个 while 就退出后面的点自然不用看了——因为这一根柱子已经把更远处的视线全部挡住。理解这个一旦不满足就停的逻辑比记住代码更重要它和 1.1 节说的可见性模型是一件事。2.3 复杂度与适用范围每个状态最多向左检查d个位置、向右检查d个位置状态数n所以总复杂度是 O(n·d)。本题的n 1000、d 1000最坏情况下循环量大约是一百万次Python 完全能扛住这也是官方推荐的第一档解法。但要注意lru_cache本身有哈希查找的开销如果数据量再放大到十万级别O(n·d) 就会直接超时。所以这道题更完整的价值在于你除了会暴力记忆化最好还能讲出优化版怎么设计。3. 优化路线单调栈预处理挡板 排序后区间最值查询3.1 先把可跳范围压缩成连续区间回到转移式dp[i] 1 max(dp[j])。如果对每个点都重新向左向右扫一遍那必然花掉 O(d)。可跳位置其实有很强的结构从i向左看最多走到i - d并且会被左边第一个大于等于arr[i]的下标挡住向右同理。换句话说可跳范围是两个连续下标区间。定义两个数组L[i]i左边第一个arr[j] arr[i]的下标不存在就是-1R[i]i右边第一个arr[j] arr[i]的下标不存在就是n。那么从i向左可跳的区间是[max(L[i] 1, i - d), i - 1]向右可跳的区间是[i 1, min(R[i] - 1, i d)]区间里的每一个点都严格矮于arr[i]因为它们都在第一个挡板之前这就是我们能放心做区间 max 查询的原因。3.2 单调栈求 L 和 R和下一个更大元素是同一套东西求左边第一个大于等于当前元素的位置用单调栈从左往右扫一遍就行核心是保持栈内高度非严格递减遇到矮的直接弹掉遇到相等的不弹否则会把最近的等高铁柱丢掉。def build_bounds(arr: List[int]) - (List[int], List[int]): n len(arr) L [-1] * n st [] for i in range(n): while st and arr[st[-1]] arr[i]: st.pop() L[i] st[-1] if st else -1 st.append(i) R [n] * n st [] for i in range(n - 1, -1, -1): while st and arr[st[-1]] arr[i]: st.pop() R[i] st[-1] if st else n st.append(i) return L, R我在这个函数里踩过的坑是弹栈条件。如果你写成arr[st[-1]] arr[i]那么遇到相等高度时会把前一个相等元素弹掉导致R[i]找不到左边最近的等高铁柱最后结果就会错。等号在本题里必须是挡住视线的角色不能随便弹出去。3.3 按高度从小到大递推同高度要分组有了区间之后问题变成了对每个i在左右两个区间里查询dp[j]的最大值再把dp[i]写入数据结构。关键问题是递推顺序。由于转移只依赖严格更矮的点我们需要保证当处理高度为h的下标时所有高度小于h的点都已经算完并写入了线段树。这个顺序天然可以通过排序实现按arr的值从小到大遍历下标。但这里藏着一个很容易写错的细节相同高度的点不能互相依赖。题目要求严格小于所以相同高度不能作为对方的转移来源。如果排序后逐个处理先处理的同高度点已经被写入了线段树后处理的同高度点就可能错误地把它当成合法状态。正确做法是把相同高度的一组下标统一处理先查询并计算这一整组所有dp值全部算完之后再统一写入线段树。order sorted(range(n), keylambda x: arr[x]) i 0 while i n: j i while j n and arr[order[j]] arr[order[i]]: j 1 # 第一遍只查询不更新 for k in range(i, j): idx order[k] best 0 l, r max(L[idx] 1, idx - d), idx - 1 if l r: best max(best, seg.query(l, r)) l, r idx 1, min(R[idx] - 1, idx d) if l r: best max(best, seg.query(l, r)) dp[idx] best 1 # 第二遍统一写入 for k in range(i, j): seg.update(order[k], dp[order[k]]) i j这个先查后更的顺序非常关键我在 4.3 节会用一个反例说明为什么漏掉它会导致答案偏大。3.4 线段树点更新 区间最大值查询现在数据结构的职责很明确支持单点更新dp[i]支持闭区间[l, r]查询最大值。这一步用线段树最直接十几行就能写完不需要任何进阶技巧。class SegTree: def __init__(self, n): self.N 1 while self.N n: self.N 1 self.tree [0] * (self.N 1) def update(self, pos, val): p pos self.N self.tree[p] max(self.tree[p], val) p 1 while p: self.tree[p] max(self.tree[p 1], self.tree[p 1 | 1]) p 1 def query(self, l, r): if l r: return 0 l self.N r self.N res 0 while l r: if l 1: res max(res, self.tree[l]) l 1 if not (r 1): res max(res, self.tree[r]) r - 1 l 1 r 1 return res这里用的是迭代式线段树N扩充到不小于n的 2 的幂。query的区间是闭区间l r时直接返回 0。整个优化版的复杂度是单调栈 O(n) 排序 O(n log n) 每次查询和更新 O(log n)总复杂度 O(n log n)空间 O(n)。这套方案即使n放大到 10 万也能轻松跑过。4. 四个容易写错的细节递归深度、等号、同高度、区间截断4.1 递归深度的坑严格递减数组直接命中默认限制记忆化搜索虽然代码短但它有一个隐藏风险递归深度。最坏情况下数组严格递减比如arr [10000, 9999, 9998, ...]你从最高点出发可以一路跳到最低点递归深度接近n。Python 的默认递归限制通常在 1000 左右n恰好是 1000 时可能刚好踩线多一点就直接RecursionError。我当时第一次提交就栽在这里。解决办法很简单在代码最上面加上import sys sys.setrecursionlimit(10 ** 6)如果面试时用的是 C/Java也要注意栈空间问题严格递减用例下递归调用可能很深。虽然本题n只有 1000 不至于爆栈但养成先考虑最坏递归深度的习惯以后遇到真正需要递归的困难题会少踩很多坑。4.2 等号必须 break不能 continue题目要求目标位置和中间位置都严格小于当前高度所以遇到arr[j] arr[i]时这一根柱子不仅不是合法目标还会像高墙一样把后面挡住。我见过不少人在初版代码里写成if arr[j] arr[i]: best max(best, dfs(j) 1) # 忘了 else break这种写法在只有一个相等高度的样例上可能还碰巧对但遇到arr [2, 2, 2]d 5这种用例就会错。正确答案是 1因为没有任何一个 2 能跳到另一个 2 上漏掉 break 的版本可能会从最左边一路跳到最右边算出 3。这也是我用来自检的边界用例全相同高度 大d如果答案不是 1代码一定有等号处理错误。4.3 排序 DP 里同高度必须分组处理再强调一次排序优化的顺序问题。假设输入是arr [2, 2, 1]d 5。如果排序后一个点一个点地处理处理高度 1 的下标 2dp[2] 1写入线段树处理下标 0高度 2查询左右区间发现下标 2 的 dp 为 1算出dp[0] 2写入处理下标 1高度 2此时线段树里已经有下标 0 的 dp 值 2如果直接查询会错误地算出dp[1] 3。但正确答案应该是dp[0] 1 max(dp[2]) 2dp[1] 1 max(dp[2]) 2。下标 0 和下标 1 都是高度 2它们之间不能互相跳。解决办法就是我 3.3 节写的两遍循环第一遍只查询这组高度相同的点的可跳区间算出 dp 暂存第二遍统一 update。这个细节如果面试官追问为什么排序后还要分组你能答出严格小于这个关键词基本就稳了。4.4 区间截断公式别写反有了L[i]和R[i]之后可跳区间很容易写错。我之前就试过把左区间直接写成[i - d, L[i]]这其实是错的因为L[i]本身高度大于等于当前点不能作为可跳点L[i] 1才可能是第一个合法位置。正确写法是left_range (max(L[i] 1, i - d), i - 1) right_range (i 1, min(R[i] - 1, i d))每次都要判断l r等于时说明这个方向没有可跳点。这类区间边界 bug 肉眼很难看出来我的经验是做完之后用暴力记忆化版本做随机小数组对拍几千组数据一跑边界问题基本都能暴露出来。5. 完整代码对照与选择建议O(n·d) 还是 O(n log n)5.1 可以直接提交的记忆化搜索完整版import sys from functools import lru_cache from typing import List sys.setrecursionlimit(10 ** 6) class Solution: def maxJumps(self, arr: List[int], d: int) - int: n len(arr) lru_cache(None) def dfs(i: int) - int: best 1 j i - 1 while j 0 and i - j d and arr[j] arr[i]: best max(best, dfs(j) 1) j - 1 j i 1 while j n and j - i d and arr[j] arr[i]: best max(best, dfs(j) 1) j 1 return best ans 0 for i in range(n): ans max(ans, dfs(i)) return ans这个版本跑n d 1000没什么压力代码短思路直接适合比赛抢时间。5.2 完整优化版单调栈 排序 线段树from typing import List class SegTree: def __init__(self, n): self.N 1 while self.N n: self.N 1 self.tree [0] * (self.N 1) def update(self, pos, val): p pos self.N self.tree[p] max(self.tree[p], val) p 1 while p: self.tree[p] max(self.tree[p 1], self.tree[p 1 | 1]) p 1 def query(self, l, r): if l r: return 0 l self.N r self.N res 0 while l r: if l 1: res max(res, self.tree[l]) l 1 if not (r 1): res max(res, self.tree[r]) r - 1 l 1 r 1 return res class Solution: def maxJumps(self, arr: List[int], d: int) - int: n len(arr) L [-1] * n st [] for i in range(n): while st and arr[st[-1]] arr[i]: st.pop() L[i] st[-1] if st else -1 st.append(i) R [n] * n st [] for i in range(n - 1, -1, -1): while st and arr[st[-1]] arr[i]: st.pop() R[i] st[-1] if st else n st.append(i) seg SegTree(n) dp [0] * n order sorted(range(n), keylambda x: arr[x]) i 0 while i n: j i while j n and arr[order[j]] arr[order[i]]: j 1 for k in range(i, j): idx order[k] best 0 l max(L[idx] 1, idx - d) r idx - 1 if l r: best max(best, seg.query(l, r)) l idx 1 r min(R[idx] - 1, idx d) if l r: best max(best, seg.query(l, r)) dp[idx] best 1 for k in range(i, j): seg.update(order[k], dp[order[k]]) i j return max(dp)这个版本核心逻辑集中在几行面试时边写边讲为什么同高度要统一更新为什么查询区间里不会有更高点就能体现出你对这道题的理解深度。5.3 两种写法的选择对比项暴力记忆化单调栈 排序 线段树时间复杂度O(n·d)O(n log n)额外空间O(n) 递归栈 哈希O(n)代码长度约 20 行约 70 行写错风险递归深度、等号 break同高度分组、区间边界、数据结构实现适用场景本题范围快速 AC数据放大到 1e5、面试展示优化思路我的实际建议是如果是比赛或者日常刷题先写暴力记忆化保底反正这题原题范围能过如果还剩时间再动手改成优化版顺便用对拍验证。面试场景则反过来讲题时先从暴力入手再自然引出单调栈和排序 DP比一上来就丢线段树代码好得多。最后分享一个我自己的调试小技巧这道题的边界条件非常多我每次改完版本都会用arr [5, 1, 4, 2], d 2手算验证一次再用arr [2, 2, 2], d 5检查等号最后跑一个随机对拍把暴力版和优化版逐一对齐。这三步走完基本上提交就不会再翻车了。