Leetcode 3660. Jump Game IX

• Leetcode 3660. Jump Game IX
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3660. Jump Game IX

1. 解题思路

不难看出，对于任意一个位置，其要跳到其所能达到的最大位置的所在，其必然是通过若干次以下操作实现：

• 跳跃至其后方比起小的元素的最远位置；
• 跳跃至其前方最大元素所在的位置；

因此，我们只需要预先计算出每一个位置前方最大的元素所在的位置以及其后方比起小的元素的最远位置，然后反复重复上述操作即可得到最终的答案。

2. 代码实现

给出python代码实现如下：

class Solution:def maxValue(self, nums: List[int]) -> List[int]:n = len(nums)pre_max = deepcopy(nums)for i in range(n-1):pre_max[i+1] = max(pre_max[i+1], pre_max[i])pre_index = [i for i in range(n)]for i in range(n-1):pre_index[i+1] = pre_index[i+1] if nums[pre_index[i+1]] >= nums[pre_index[i]] else pre_index[i]elems = [(i, num) for i, num in enumerate(nums)]elems = sorted(elems, key=lambda x: (x[1], x[0]))post_index = [i for i in range(n)]max_idx = -1for idx, num in elems:max_idx = max(max_idx, idx)post_index[idx] = max_idx@lru_cache(None)def dp(idx):if post_index[pre_index[idx]] == idx:return idxreturn dp(post_index[pre_index[idx]])ans = [dp(i) for i in range(n)]return [pre_max[idx] for idx in ans]

提交代码评测得到：耗时1447ms，占用内存173.40MB。