0975. 奇偶跳

ITCharge大约 5 分钟

---

0975. 奇偶跳

标签：栈、数组、动态规划、有序集合、排序、单调栈
难度：困难

题目链接

0975. 奇偶跳 - 力扣

题目大意

描述：

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

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

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

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

要求：

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

说明：

$1 \le arr.length \le 20000$ 。
$0 \le arr[i] \lt 10^{0000}$ 。

示例：

示例 1：

输入：[10,13,12,14,15]
输出：2
解释： 
从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 arr[2] 是 arr[1]，arr[2]，arr[3]，arr[4] 中大于或等于 arr[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，因为 arr[1] 是（arr[1]，arr[2]，arr[3]，arr[4]）中大于或等于 arr[0] 的最小值。

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

在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 arr[3] 是（arr[3]，arr[4]）中大于或等于 arr[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）出发，通过一定数量的跳跃到达数组末尾。

解题思路

思路 1：动态规划 + 单调栈

这是一道困难的动态规划问题，需要结合单调栈来优化。

状态定义：
- $odd[i]$ ：从位置 $i$ 开始，第一次跳跃是奇数跳，能否到达终点
- $even[i]$ ：从位置 $i$ 开始，第一次跳跃是偶数跳，能否到达终点
状态转移：
- 奇数跳：跳到满足 $arr[j] \ge arr[i]$ 且 $arr[j]$ 最小的位置 $j$
- 偶数跳：跳到满足 $arr[j] \le arr[i]$ 且 $arr[j]$ 最大的位置 $j$
单调栈优化：使用单调栈预处理每个位置的下一跳位置。
从后向前 DP：从最后一个位置开始，逐步计算每个位置的状态。

思路 1：代码

class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        n = len(arr)
        
        # 计算下一跳位置
        def make_next(sorted_indices):
            """使用单调栈计算下一跳位置"""
            result = [None] * n
            stack = []
            for i in sorted_indices:
                while stack and i > stack[-1]:
                    result[stack.pop()] = i
                stack.append(i)
            return result
        
        # 奇数跳：按值升序，索引升序排序
        odd_next = make_next(sorted(range(n), key=lambda i: (arr[i], i)))
        
        # 偶数跳：按值降序，索引升序排序
        even_next = make_next(sorted(range(n), key=lambda i: (-arr[i], i)))
        
        # DP：从后向前计算
        odd = [False] * n
        even = [False] * n
        odd[n - 1] = even[n - 1] = True
        
        for i in range(n - 2, -1, -1):
            if odd_next[i] is not None:
                odd[i] = even[odd_next[i]]
            if even_next[i] is not None:
                even[i] = odd[even_next[i]]
        
        # 统计从奇数跳开始能到达终点的位置数
        return sum(odd)

思路 1：复杂度分析

时间复杂度： $O(n \log n)$ ，其中 $n$ 是数组长度。排序需要 $O(n \log n)$ ，单调栈和 DP 都是 $O(n)$ 。
空间复杂度： $O(n)$ ，需要存储下一跳位置和 DP 状态。