LeetCode 每日一题笔记 日期：2026.05.24 题目：1340. 跳跃游戏 V

LeetCode 每日一题笔记0. 前言日期2026.05.24题目1340. 跳跃游戏 V难度困难标签数组、动态规划、记忆化搜索、单调栈1. 题目理解问题描述给定一个整数数组arr和整数d从下标i出发每次可以向左或向右跳1~d步。跳跃规则为只能跳到比当前位置更低的位置且路径中不能出现比当前位置更高的元素。你可以从任意下标开始返回最多可以访问的下标数量。示例输入arr [6,4,14,6,8,13,9,7,10,6,12], d 2输出4解释以arr[10]12为起点路径为12→10→9→7共访问 4 个下标。2. 解题思路核心观察从i能跳到的位置只能是i左右两侧[i-d, id]范围内、且路径中无更高元素的更低位置。这是一个典型的“树形依赖”问题每个位置的最长跳跃路径依赖于它能跳到的位置的最长路径因此可以用记忆化搜索递归DP解决。为了优化时间复杂度可先用单调栈预处理每个位置左右最近的更高元素直接找到能跳的终点避免遍历中间所有元素。算法步骤基础版记忆化搜索定义dp[i]表示从i出发能访问的最大下标数。递归遍历每个位置i分别向左、向右检查1~d步的所有位置遇到更高元素则停止。用dp[i] max(dp[j]) 1转移其中j是i能跳到的位置。用dp数组缓存结果避免重复计算。优化版单调栈记忆化用单调栈预处理每个位置i左右两侧、距离不超过d的最近更高元素left[i]和right[i]。从i只能跳到left[i]和right[i]之间的更低位置因此递归时直接跳转无需遍历中间元素。用memo[i]缓存结果时间复杂度从 O(n·d) 优化到 O(n)。3. 代码实现packagelc1340;importjava.util.Arrays;publicclassSolution{intjump(int[]arr,int[]dp,inti,intd){if(dp[i]!-1)returndp[i];intres1;intrightMath.min(arr.length-1,id);intleftMath.max(0,i-d);// 向左跳for(intji-1;jleft;j--){if(arr[j]arr[i])break;resMath.max(res,jump(arr,dp,j,d)1);}// 向右跳for(intji1;jright;j){if(arr[j]arr[i])break;resMath.max(res,jump(arr,dp,j,d)1);}dp[i]res;returnres;}publicintmaxJumps(int[]arr,intd){intdp[]newint[arr.length];Arrays.fill(dp,-1);intres1;for(inti0;iarr.length;i){resMath.max(res,jump(arr,dp,i,d));}returnres;}}4. 代码优化说明classSolution{publicintmaxJumps(int[]arr,intd){intnarr.length;// 计算 arr[i] 左边最近的更高元素 arr[left[i]]int[]leftnewint[n];int[]stnewint[n];inttop-1;// 栈顶下标for(inti0;in;i){intxarr[i];while(top0arr[st[top]]x){top--;// 出栈}// 如果左边没有更高的数或者跳跃距离超过 d都标记为 -1left[i]top0||i-st[top]d?-1:st[top];st[top]i;// 入栈}// 计算 arr[i] 右边最近的更高元素 arr[right[i]]int[]rightnewint[n];top-1;for(intin-1;i0;i--){intxarr[i];while(top0arr[st[top]]x){top--;}// 如果右边没有更高的数或者跳跃距离超过 d都标记为 -1right[i]top0||st[top]-id?-1:st[top];st[top]i;}int[]memonewint[n];// 枚举终点倒着跳intans0;for(inti0;in;i){ansMath.max(ans,dfs(i,left,right,memo));}returnans;}privateintdfs(inti,int[]left,int[]right,int[]memo){if(memo[i]0){// 没有计算过// 往左跳 vs 往右跳intlleft[i]-1?0:dfs(left[i],left,right,memo);intrright[i]-1?0:dfs(right[i],left,right,memo);memo[i]Math.max(l,r)1;}returnmemo[i];}}优化说明用单调栈预处理left和right数组避免递归中遍历1~d步的所有元素直接找到能跳的终点。简化dfs中的if分支判断用三元运算符处理left[i]和right[i]为-1的情况。时间复杂度从 O(n·d) 优化到 O(n)空间复杂度为 O(n)避免了大规模用例的超时问题。5. 复杂度分析基础版时间复杂度O(n·d)每个位置最多遍历d步且每个位置仅计算一次。空间复杂度O(n)递归栈深度和dp数组均为 O(n)。优化版时间复杂度O(n)单调栈预处理和记忆化搜索均为线性时间。空间复杂度O(n)left、right、memo数组和单调栈均为 O(n)。6. 总结本题核心是利用记忆化搜索解决树形依赖问题基础版实现简单但易超时优化版通过单调栈预处理大幅降低时间复杂度。解题关键在于理解“路径中无更高元素”的规则通过预处理找到能跳的终点避免不必要的遍历。对于大规模用例优先使用优化版基础版适合快速实现和理解问题。