跳跃游戏 V

标签: 数组 动态规划 排序

难度: Hard

给你一个整数数组 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

Submission

运行时间: 55 ms

内存: 16.1 MB

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

        #     for j in range(i + 1,min(n - 1,i + d) + 1):
        #         if arr[j] >= arr[i]:
        #             break
        #         ans = max(ans,dfs(j) + 1)
        #     return ans
        
        # return max(dfs(i) for i in range(n)) + 1



class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        # 在最右侧添加一个无穷大高的柱子, 目的是为了让原先的元素全部出栈
        dp = [1] * (n + 1) 
        stack = []
        for i, a in enumerate(arr + [float("inf")]):
            while stack and arr[stack[-1]] < a:
                L = [stack.pop()]
                while stack and arr[stack[-1]] == arr[L[0]]:
                    L.append(stack.pop())
                for j in L:
                    # j被弹出来的时候, 更新右边i的dp
                    if i - j <= d:
                        dp[i] = max(dp[i], dp[j] + 1)
                        
                    # j被弹出来的时候, 更新左边的元素的dp
                    if stack and j - stack[-1] <= d:
                        # 为什么只更新了stack[-1]的dp? stack[-2]以及更左边的dp, 怎么办?
                        # 不用担心, 当stack[-1]被弹出里的时候, 会更新stack[-2]的dp.
                        # stack[-2]被弹出来的时候, 会更新stack[-3]
                        dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)
            stack.append(i)
        return max(dp[:-1])

Explain

题解采用了单调栈的方法来解决问题。首先，我们创建一个长度为n+1的dp数组，初始值为1，表示每个下标最少可以访问1个位置。然后，遍历数组，并维护一个单调递增的栈。遍历时，如果当前元素大于栈顶元素，则开始处理栈中的元素。对于每个被弹出的栈中元素，我们更新它的右侧最远可跳位置，并尝试更新它左侧元素的dp值。处理完所有元素后，栈顶元素的dp值就是我们需要的结果。这种方法的关键在于，通过维护一个单调栈，我们能够有效地处理每个元素左右可跳的最大范围，从而动态地更新dp数组。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        dp = [1] * (n + 1)  # 创建dp数组，初始化每个位置的最小可跳跃次数为1
        stack = [] # 初始化栈，用于存储下标
        for i, a in enumerate(arr + [float('inf')]): # 遍历数组，包含一个哨兵元素
            while stack and arr[stack[-1]] < a: # 当前元素大于栈顶元素时处理栈中元素
                L = [stack.pop()]
                while stack and arr[stack[-1]] == arr[L[0]]: # 处理相等元素的情况
                    L.append(stack.pop())
                for j in L: # 更新dp值
                    if i - j <= d:
                        dp[i] = max(dp[i], dp[j] + 1) # 更新右侧元素的dp值
                    if stack and j - stack[-1] <= d:
                        dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1) # 更新左侧元素的dp值
            stack.append(i) # 当前元素入栈
        return max(dp[:-1]) # 返回最大的dp值

Explore

在单调栈中，我们通过维持一个单调递增的栈结构，确保栈中的每个元素都是小于当前遍历到的元素`arr[i]`的。当`arr[i]`大于栈顶元素时，栈顶元素会被弹出，这时候，栈顶元素`j`之前的元素（即新的栈顶元素）一定是小于`arr[j]`的，因为栈是单调递增的。这确保了我们处理的是`arr[i] > arr[k]`的条件，其中`k`是`j`和`i`之间的任意下标。

添加哨兵元素`float('inf')`到数组的末尾的目的是为了在最后一个元素处理完后，能够确保栈中所有剩余的元素都能被正确处理。由于`float('inf')`大于任何其它元素，这保证了在数组全部遍历完毕时，栈中的元素将会依次被弹出并进行最后的更新操作。这样做简化了代码的复杂度，避免了在循环结束后还需要单独处理栈中剩余元素的情况。

在`arr[i]`和`arr[j]`之间如果存在多个相同元素，这些元素会连续地被压入栈中。当遇到一个大于这些相同元素的`arr[i]`时，这些相同元素将会一起被处理。在弹出这些元素时，我们将它们存储在一个列表中，并一起更新它们的dp值。这种处理确保了在相同值的情况下，每个元素的最远跳跃距离和左侧元素的更新都能正确地计算，从而不会错过任何一个更新机会。

在更新dp数组时，为了避免重复计算或者错过更新，我们需要保证每次只有在满足跳跃条件的情况下才进行更新。具体来说，只有当`i - j <= d`时，我们才更新`dp[i]`。类似地，只有当`j - stack[-1] <= d`时，我们才更新`stack[-1]`的dp值。这样的条件检查确保了我们不会在跳跃距离超过`d`的情况下错误地进行更新，同时也避免了对同一个dp值的多次无效更新。