当前位置: 代码迷 >> 综合 >> leetcode-1340. 跳跃游戏 V
  详细解决方案

leetcode-1340. 跳跃游戏 V

热度:91   发布时间:2024-02-08 01:55:33.0

题目

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

解题思路

拓扑排序。

若下标i可以跳到下标j,则认为有一条ij的有向边。从没有出边的节点开始计算,对没有出边的节点j,令f(j) = 1,然后f(i) = 1 + max([f(N1), f(N2), ...]),其中N1, N2i的出边指向的所有节点。

时间复杂度 o ( n ) o(n)

代码

class Solution:def maxJumps(self, arr: List[int], d: int) -> int:graph = {index: {'outdegree': 0, 'out_neighbor': [], 'in_neighbor': []} for index in range(len(arr))}for index, num in enumerate(arr):left_index, right_index = index - 1, index + 1while left_index >= 0 and left_index >= index - d:if arr[left_index] < num:graph[left_index]['in_neighbor'].append(index)graph[index]['outdegree'] += 1graph[index]['out_neighbor'].append(left_index)left_index -= 1else:breakwhile right_index < len(arr) and right_index <= index + d:if arr[right_index] < num:graph[right_index]['in_neighbor'].append(index)graph[index]['outdegree'] += 1graph[index]['out_neighbor'].append(right_index)right_index += 1else:breakqueue = collections.deque([(node, 1) for node, val in graph.items() if val['outdegree'] == 0])cnt = 0index_dict = {}while queue:node, path = queue.popleft()index_dict[node] = max([index_dict[neighbor] for neighbor in graph[node]['out_neighbor']] + [path])cnt = max(cnt, path)for in_neighbor in graph[node]['in_neighbor']:graph[in_neighbor]['outdegree'] -= 1if graph[in_neighbor]['outdegree'] == 0:queue.append((in_neighbor, path + 1))return cnt