1340：跳跃游戏 V（1866 分）

2020-02-02 约 930 字预计阅读 2 分钟次阅读

力扣第 174 场周赛第 4 题

题目

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：

i + x ，其中 i + x < arr.length 且 0 < x <= d 。
i - x ，其中 i - x >= 0 且 0 < x <= d 。

除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。

你可以选择数组的任意下标开始跳跃。请你返回你最多可以访问多少个下标。

请注意，任何时刻你都不能跳到数组的外面。

示例 1：

输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。

示例 2：

输入：arr = [3,3,3,3,3], d = 3
输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。

示例 3：

输入：arr = [7,6,5,4,3,2,1], d = 1
输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。

示例 4：

输入：arr = [7,1,7,1,7,1], d = 2
输出：2

示例 5：

输入：arr = [66], d = 1
输出：1

提示：

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

相似问题：

分析

#1 dp

跳的路径严格递减，因此可以递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        @cache
        def dfs(i):
            res = 1
            for j in range(i+1,i+d+1):
                if j>=n or arr[j]>=arr[i]:
                    break
                res = max(res, 1+dfs(j))
            for j in range(i-1,i-d-1,-1):
                if j<0 or arr[j]>=arr[i]:
                    break
                res = max(res, 1+dfs(j))
            return res
        
        n = len(arr)
        return max(dfs(i) for i in range(n))

371 ms

#2 单调栈

还可以反过来，从低到高考虑路径
对于位置 j，最优的路径一定是跳到上/下一个更大位置
- 如果该位置的距离超出了 d，则不能跳
因此，用单调栈求出上/下一个更大位置，即可递归

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        sk,L = [],[-1]*n
        for i,x in enumerate(arr):
            while sk and arr[sk[-1]]<=x:
                sk.pop()
            if sk and i-sk[-1]<=d:
                L[i] = sk[-1]
            sk.append(i)
        sk,R = [],[-1]*n
        for i,x in enumerate(arr):
            while sk and arr[sk[-1]]<x:
                j = sk.pop()
                if i-j<=d:
                    R[j] = i
            sk.append(i)
        @cache
        def dfs(i):
            if i<0:
                return 0
            return 1+max(dfs(L[i]),dfs(R[i]))
        return max(dfs(i) for i in range(n))

45 ms

#3

事实上，可以一次单调栈同时求出上/下一个更大位置
- 只要将相同的值一起处理即可
在单调栈过程中可同时进行递推

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        arr.append(inf)
        n = len(arr)
        f = [1]*n
        sk = []
        for i,a in enumerate(arr):
            while sk and arr[sk[-1]]<a:
                A = [sk.pop()]
                while sk and arr[sk[-1]]==arr[A[0]]:
                    A.append(sk.pop())
                for j in A:
                    if i-j<=d and 1+f[j]>f[i]:
                        f[i] = 1+f[j]
                    if sk and j-sk[-1]<=d and 1+f[j]>f[sk[-1]]:
                        f[sk[-1]] = 1+f[j]
            sk.append(i)
        return max(f[:-1])

16 ms

目录

1340：跳跃游戏 V（1866 分）

题目

分析

#1 dp

#2 单调栈

#3

解答