刷题群里又在讨论今天的每日一题点开一看是跳跃游戏Ⅳ。题目用 go 语言实现其实很顺手给一个整数数组 nums从任意起点索引 i 出发每次移动到更大的下标 j并且要求目标位置的值比当前位严格更大。这题一眼看是图论再一眼看是 LIS最后落到手头还是一道动态规划。这篇文章把我在 go 里从 O(n²) 暴力到 O(n log n) 贪心二分的完整思路、代码、坑位都记录一遍给同样在啃跳跃类题目的朋友做个参考。1. 题目与建模先搞清楚“跳”的本质1.1 完整题干与我的理解题面原始描述被截断在“目标位置的值必须比当前位”补全之后完整规则是这样的你有一个整数数组nums对于任意起点索引i可以多次向右移动到更大的下标j且要求nums[j]严格大于nums[i]。问在这种规则下从某个起点出发最多能连续跳多少次或者说最多能经过多少个位置。这里有几个关键点需要注意。第一“向右走”意味着索引单调递增整个跳跃过程不回头所以不存在环。第二“目标值必须严格大于当前值”意味着数值上也是单调递增的。一个递增索引、一个递增数值两个约束叠加起来本质上就是“在一个序列里找一个索引和值都递增的子序列并且让它尽可能长”。这不就是经典的 LIS最长递增子序列问题么。很多朋友一上来就想着建图跑 DFS 或者 BFS其实没必要。因为题目给的两个约束已经把图固定成了一个 DAG有向无环图并且这个 DAG 的形态非常特殊——每个节点只会指向右侧且值更大的节点。在这种特殊 DAG 上求最长路径最自然的工具就是动态规划或者直接用 LIS 的贪心二分优化。1.2 抽象成状态dp[j] 到底代表什么我最初的直觉是先定义状态。设dp[j]表示“以nums[j]作为当前落脚点能形成的最大跳跃链长度”。注意是“长度”不是“步数”。如果链上有 3 个节点那么跳跃次数就是 2不同题目问法不同代码里最后返回时要留意减不减这个 1。转移方程也很直接dp[j] max(dp[i] 1)条件是i j且nums[i] nums[j]。初始的时候每个位置都能单独作为一个长度为 1 的链所以dp[i] 1。这个转移的含义是我在跳向j之前最后一步从i过来那么整体链长就是以前i结尾的链长再加 1。我自己在纸上推了一个例子nums [1, 3, 2, 4]。从 0 出发1 可以跳到 3、2、4但 3 和 2 又都能跳到 4。手工算一下最长链是1 - 2 - 4或者1 - 3 - 4长度都是 3跳跃次数是 2。这个例子简单但足够用来验证后面代码逻辑是否走偏。2. 解法一动态规划 O(n²)——先保证正确性2.1 双层循环的转移怎么写如果只求“能走多长”O(n²) 的 DP 是最好写也最不容易出错的方案。外层循环枚举当前落脚点j内层循环枚举可能的前驱i。每来一个j我就回头扫一遍之前的所有位置看哪些位置的值严格小于nums[j]有的话就用“前驱链长 1”来尝试更新当前链长。这个思路跟最长递增子序列的常规 DP 完全一致。很多人会问为什么内层循环是i从 0 到j-1而不是从j-1到 0其实方向无所谓因为我们要遍历所有可能的前驱顺序不会影响最终结果。但从前向后扫有一个额外好处配合“只在nums[i] nums[j]时更新”这个条件代码读起来更符合自然思维。完整的 Go 实现长这样func maxJumpsDP(nums []int) int { n : len(nums) if n 0 { return 0 } // dp[i] 表示以 i 结尾的最长合法链长度 dp : make([]int, n) for i : 0; i n; i { dp[i] 1 } ans : 1 for j : 1; j n; j { for i : 0; i j; i { if nums[i] nums[j] dp[i]1 dp[j] { dp[j] dp[i] 1 } } if dp[j] ans { ans dp[j] } } return ans }这段代码有几个地方值得强调。初始化dp[i] 1是因为任何单个位置都是合法链ans初始化为 1 是因为数组至少有一个元素时最长链长度至少为 1。如果题目允许空数组且要求返回 0那么开头那个n 0判断就是必需的。如果题目问的是“最大跳跃次数”记得把ans减 1。2.2 时间复杂度与适用场景O(n²) 的复杂度在面试中能不能过关取决于数据范围。如果n在 10³ 量级这个写法完全没问题一旦n到了 10⁵ 甚至 10⁶2 层循环就是灾难必须换思路。实测本地跑起来n 10^4时双层循环还能勉强接受n 10^5时基本就要等好几秒。所以我的习惯是小数据量或者笔试时间紧张时先写 DP 保证正确拿到基础分如果一眼看出题目数据范围很大直接跳到贪心二分。毕竟算法题不仅要求“能跑”还要求“跑得过”。3. 解法二贪心 二分 O(n log n)——把 LIS 的板子搬过来3.1 tails 数组为什么能用二分O(n log n) 的核心是维护一个tails数组。tails[k]表示“长度为 k1 的所有递增子序列中末尾元素的最小值”。这个定义有点绕举个生活例子你是面试官要选一条最长的递增团队链每个人必须比前一个人能力强值更大。tails[k]就是“已经组建了长度为 k1 的链时最后一个人能力最弱是多少”。尾巴的价值越小后面能接的人就越多这是贪心思想的精髓。遍历nums时对当前值v我在tails里找到第一个大于等于v的位置把那个位置的尾巴替换成v。如果v比tails里所有尾巴都大就追加到末尾最长链长度加一。为什么找第一个“大于等于”而不是“大于”因为题目要求严格递增如果我替换的是“等于”的位置就把相同值保留在链里了后面的更新还能继续收紧如果我替换的是“大于”的位置可能出现tails里两个相同值导致后续判断出错。这里有一个新手非常容易踩的坑把“严格递增”写成“非递减”。一旦允许相等二分查找的边界条件就得从改成整个结果就错了。3.2 Go 实现sort.Search 与手写二分Go 标准库的sort.Search可以直接用来做二分查找代码非常短func maxJumpsLIS(nums []int) int { tails : make([]int, 0, len(nums)) for _, v : range nums { // 找第一个 v 的位置 pos : sort.Search(len(tails), func(i int) bool { return tails[i] v }) if pos len(tails) { tails append(tails, v) } else { tails[pos] v } } return len(tails) }如果你不想依赖sort.Search手写二分也就十行左右func upperBound(tails []int, v int) int { lo, hi : 0, len(tails) for lo hi { mid : (lo hi) / 2 if tails[mid] v { hi mid } else { lo mid 1 } } return lo }两种写法效果一样。sort.Search的闭包写法第一次看可能不习惯但它返回的是满足条件的最小下标边界情况处理得比我手写更稳妥。我平时在比赛里更倾向于手写二分因为少一次闭包调用性能上略微好一点不过在n 10^5这个量级上区别微乎其微。3.3 从“任意起点”到“固定起点 0”的变体原题说“任意起点索引 i”所以上面求的是整个数组的全局最长链。但有些变体会把起点固定成0问你从 0 出发最多能跳多远。这个变体稍微绕一下起点固定后第一站必须是nums[0]之后所有落脚点的值都必须大于nums[0]而且索引必须在0之后。我当时的处理思路是先把nums[1:]里所有小于等于nums[0]的元素过滤掉再对剩下的部分求 LIS最后加 1 把起点算进去。这样做的正确性在于过滤不会改变剩下元素之间的相对顺序也不会影响它们在原数组里的索引先后关系只排除了不可能作为后继的值。func maxJumpsFromStart(nums []int) int { if len(nums) 0 { return 0 } if len(nums) 1 { return 1 } candidates : make([]int, 0, len(nums)-1) for _, v : range nums[1:] { if v nums[0] { candidates append(candidates, v) } } return maxJumpsLIS(candidates) 1 }注意这里求的是“经过的位置数量”不是“跳跃次数”。如果面试官问的是步数答案要减 1。这类细节我建议在看完题面后第一时间确认别等写完代码才发现。4. 边界情况、常见错误与排查实录4.1 等号问题严格大于还是大于等于这是这题埋得最深的坑。题目描述写的是“目标位置的值必须比当前位大”也就是严格大于。所以nums[i] nums[j]时不能跳。用 DP 写法时条件是nums[i] nums[j]用贪心二分时sort.Search的判定是tails[i] v。很多人在 LeetCode 上提交失败十有八九是把严格递增写成了非递减。我曾经在nums [2, 2, 3]这个用例上翻过车。如果允许相等值跳跃最长链是2 - 3长度 2如果严格递增最长链还是2 - 3好像区别不大。但是换成nums [1, 1, 1]允许等值的答案是 3严格递增的答案只能是 1。测试用例一旦铺开这个差别立刻暴露。4.2 空数组和单元素数组的处理空数组怎么返回取决于题目约定。一般 LIS 类的题会返回 0我习惯在一开始就做防御性判断。单元素数组更简单最长链长度就是 1跳跃次数是 0因为根本没有动过。还有一个容易被忽略的情况终点值比起点值小或相等。如果起点固定在 0且所有后续元素都不大于nums[0]那么candidates为空maxJumpsLIS返回 0最后结果加 1 变成 1。这个“1”代表我只能停留在起点跳不出去这个语义是对的。4.3 我给初学者排查三连问如果你写完代码跑测试不过我建议按下面三个问题逐步排查。第一dp数组初始化了吗很多人声明了切片就默认它是全 0但 Go 里零值可不会自己变成 1。初始化成 1 是最常见的隐含条件。第二比较符号有没有写反nums[i] nums[j]和nums[i] nums[j]只差一个字符输出的结果可能天差地别。第三最后返回的是长度还是步数如果题目问最小跳跃次数、最大跳跃次数而你的返回值是链长度记得统一减一。我把这些问题整理成了一张自查表情况正确做法常见错误严格递增判定nums[i] nums[j]写成二分查找边界找第一个 v的位置找第一个 v的位置空数组n 0时返回 0直接下标访问 panic单元素数组长度 1步数 0误返回 0返回长度还是步数看题目要求混淆后多减一5. 延伸索引思维、数据库索引与刷题联想5.1 LIS 的 tails 和数据库索引的共同点刷完这题再回头看热搜词里的 MySQL 索引、索引表空间之类的话题我突然觉得tails数组的维护方式跟数据库索引有几分神似。tails维护的是一个有序序列每次插入一个新值时用二分查找定位这跟 B 树索引的查找方式本质上是同一套思维有序、二分、局部更新。当然这只是个类比实际工程里数据库索引要考虑磁盘页、回表、联合索引的最左匹配、覆盖索引等等比算法题里的数组复杂得多。但如果你刚用 Go 刷完 LIS再去看 MySQL 里“where 条件 a and b 应该怎么建索引”你会发现共同点都是“如何让数据按某种有序结构组织从而减少搜索范围”。5.2 如果题目改成“求最小步数”会怎样这题很容易被人误读成“最短跳跃步数”。我一开始也以为要跑 BFS但仔细想了一下这个规则的特殊性只要终点值比起点值大我完全可以直接从起点一步跳到终点因为题目没有限制“只能跳相邻”或“最多跳多远”。所以这个规则下最小步数要么是 0起点就是终点要么是 1终点值大于起点值要么根本不可达终点值不大于起点值。这个结论反过来验证了模型的重要性——如果你把它当成 BFS 来写代码复杂度上去了结果还可能是错的。5.3 二维跳跃、带权值的后续扩展如果面试官想继续加码可能会把一维数组改成二维矩阵问从左上角往右下角走每次只能向右或向下且目标值必须严格大于当前值求最长路径。这时候 DP 状态变成二维dp[i][j]依赖dp[i-1][j]和dp[i][j-1]转移顺序要按行、列递增来。还有一个变体是给每个位置加权重跳跃得分不只是长度而是经过位置权重的累加这种就得改成带权 DAG 上的最长路径问题通常用拓扑排序配合 DP 解决。这些扩展万变不离其宗核心都是“索引约束 数值约束”两个维度的组合。你把这两个约束拆开分别建模很多看似吓人的题其实都是 LIS 的套壳。6. 从我这次实操中学到的三件事第一件遇到“跳跃”类题目不要条件反射式地只想到 BFS。先看移动规则如果只能朝一个方向走并且建立了一个偏序关系大概率是 LIS 的变体。第二件Go 的sort.Search很好用但前提是你理解它返回的“第一个满足条件的位置”到底是什么手写二分虽然多几行但排查问题时更直观我建议两种写法都练熟。第三件接题第一件事永远是确认“能不能原地不动、能不能相等值跳跃、返回的是长度还是步数”这三个问题的答案直接决定边界条件的写法。这题我自己从读题到写下 O(n log n) 解法大概花了十分钟中间在“固定起点”这个变体上多绕了几分钟。但弄清楚之后再回看原来的 DP 代码会觉得一切都很自然。如果你也在刷跳跃游戏系列建议把Ⅰ、Ⅱ、Ⅳ放一起对比着做你会发现同样的关键词“跳跃”底层模型完全不同Ⅰ是区间覆盖贪心Ⅱ是 BFS 分层Ⅳ是偏序上的 LIS。搞懂这一点比记住单独某道题的代码有价值得多。