0975：奇偶跳（2079 分）

力扣第 119 场周赛第 4 题

题目

给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为偶数跳跃。

你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：

• 在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引 j，使得 A[i] <= A[j]，A[j] 是可能的最小值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
• 在进行偶数跳跃时（如，第 2，4，6... 次跳跃），你将会跳到索引 j，使得 A[i] >= A[j]，A[j] 是可能的最大值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
• （对于某些索引 i，可能无法进行合乎要求的跳跃。）

如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 A.length - 1），那么该索引就会被认为是好的起始索引。

返回好的起始索引的数量。

示例 1：

输入：[10,13,12,14,15]
输出：2
解释： 
从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 A[2] 是 A[1]，A[2]，A[3]，A[4] 中大于或等于 A[0] 的最小值），然后我们就无法继续跳下去了。
从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。
从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。

示例 2：

输入：[2,3,1,1,4]
输出：3
解释：
从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：

在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 A[1] 是（A[1]，A[2]，A[3]，A[4]）中大于或等于 A[0] 的最小值。

在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 A[2] 是（A[2]，A[3]，A[4]）中小于或等于 A[1] 的最大值。A[3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。

在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 A[3] 是（A[3]，A[4]）中大于或等于 A[2] 的最小值。

我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。

类似地，我们可以推断：
从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。

示例 3：

输入：[5,1,3,4,2]
输出：3
解释： 
我们可以从起始索引 1，2，4 出发到达数组末尾。

提示：

1. 1 <= A.length <= 20000
2. 0 <= A[i] < 100000

分析

#1

显然每个位置的奇数跳和偶数跳都是确定的，考虑先求出来。

奇数跳是先在 i 右边找到最接近的较大值，再从中选最接近的位置。 容易想到，可以维护一个有序列表 tmp，将位置 [i+1, n-1] 按 (值 A[x] 升序、位置 x 升序）排序，然后二分查找第一个大于等于 A[i] 的位置 tmp[pos] 即可。 找到后，将 i 插入到 tmp 的 pos 处即可维护 tmp。

同理，对于偶数跳，维护 tmp 将位置 [i+1, n-1] 按 (值 A[x] 升序、位置 x 降序）排序，然后二分查找最后一个小于等于 A[i] 的位置 tmp[pos]。 将 i 插入到 tmp 的 pos+1 处即可维护 tmp。

得到两个数组 odd 和 even 后（找不到的置为 n），就可以递推得到每个位置能否跳到末尾了。令 dp[i][0] 代表从 i 位置先奇数跳能否到达末尾， dp[i][1] 代表从 i 位置先偶数跳能否到达末尾，状态转移方程为：

if i == n:		dp[i] = [False, False]
elif i == n-1:	dp[i] = [True, True]
else:			dp[i][0] = dp[odd[i]][1], dp[i][1] = dp[even[i]][0]

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

def oddEvenJumps(self, arr: List[int]) -> int:
	n = len(arr)
	odd, tmp = [n] * n, []
	self.__class__.__getitem__ = lambda self, x: arr[tmp[x]] >= arr[i]
	for i in range(n-1, -1, -1):
		pos = bisect_left(self, True, 0, len(tmp))
		odd[i] = tmp[pos] if pos != len(tmp) else n
		tmp.insert(pos, i)
	even, tmp = [n] * n, []
	self.__class__.__getitem__ = lambda self, x: arr[tmp[x]] > arr[i]
	for i in range(n-1, -1, -1):
		pos = bisect_left(self, True, 0, len(tmp))
		even[i] = tmp[pos-1] if pos else n
		tmp.insert(pos, i)
	dp = [[i == n-1]*2 for i in range(n+1)]
	for i in range(n-2, -1, - 1):
		dp[i][0] = dp[odd[i]][1]
		dp[i][1] = dp[even[i]][0]
	return sum(dp[i][0] for i in range(n))

960 ms

#2

求奇数跳和偶数跳有个巧妙的单调栈解法。

先将位置 [0, n-1] 按 (值 A[x] 升序、位置 x 升序）排序得到 tmp，那么奇数跳就是求每个元素 在 tmp 中的下一个更大元素。 同理，将位置 [0, n-1] 按 (值 A[x] 降序、位置 x 升序）排序得到 tmp，那么偶数跳就是求每个元素 在 tmp 中的下一个更大元素。

找下一个更大元素，即是单调栈的典型应用，类似 0739。

解答

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

def oddEvenJumps(self, arr: List[int]) -> int:
	def nxt(A):
		res, stack = [n] * n, []
		for i in A:
			while stack and stack[-1] < i:
				res[stack.pop()] = i
			stack.append(i)
		return res

	n = len(arr)
	odd = nxt(sorted(range(n), key=lambda i: arr[i]))
	even = nxt(sorted(range(n), key=lambda i: -arr[i]))
	dp = [[i == n-1]*2 for i in range(n+1)]
	for i in range(n-2, -1, - 1):
		dp[i][0] = dp[odd[i]][1]
		dp[i][1] = dp[even[i]][0]
	return sum(dp[i][0] for i in range(n))

200 ms