1340. Jump Game V

题目信息

题号:

1340

难度:

Hard

主题:

数组、动态规划、深度优先搜索

原题:

LeetCode 1340

重点:

可向左右最多 d 格跳到严格更小的值;路径中间若出现大于等于当前值的元素会阻挡该方向

题目重述

给定整数数组 arr 和最大跳跃距离 d。从下标 i 可以向左或向右跳到距离不超过 d 的下标 j,条件是 arr[j] < arr[i],并且 i 与 j 之间所有位置的值也都严格小于 arr[i]。

可以从任意下标开始。请返回一次跳跃序列最多能够访问的下标数量,起始下标也计入。

1 <= arr.length <= 1000,1 <= arr[i] <= 10^5,1 <= d <= arr.length。

自建示例

严格下降序列可以逐项访问:

输入:arr = [7,6,5,4], d = 2
输出:4
解释:可以按 0 -> 1 -> 2 -> 3 跳跃,共访问四个位置。

相等高度不能作为目标也会阻挡:

输入:arr = [3,3], d = 1
输出:1
解释:任一位置都不能跳到另一个相等值位置。