# 0975. 奇偶跳

### 题目地址 (975. 奇偶跳）

<https://leetcode-cn.com/problems/odd-even-jump/>

### 题目描述

```
给定一个整数数组 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 <= A.length <= 20000
0 <= A[i] < 100000

```

### 前置知识

* [单调栈](/leetcode-solution/thinkings/monotone-stack.md)

### 公司

* 暂无

### 思路

题目要求我们从数组某一个索引出发交替跳高和跳低（奇偶跳），如果可以跳到末尾，则计数器加一，最终返回计数器的值。

这种题目一般都是倒着思考比较容易。因为我虽然不知道你**从哪开始**可以跳到最后，但是我知道最终被计算进返回值的一定是在数组末尾**结束的**。

我们先尝试从题目给的例子打开思路。

以题目中的\[10,13,12,14,15]为例。最终计入计数器的出发点一定是跳到了 15 上，15 这一步既可以是跳高（奇数跳）过来的，也可以是跳低（偶数跳）过来的。

* 如果是跳高过来的，那么一定是 14，因此只有 14 的下一个**最小的**比其大（或等于）的是 15。
* 不可能是跳低过来的，因为没有比它大的。而如果前面有比它大的，那一定是找一个数 x，x 的下一个**最大**的比其小（或等于）的是 15。

一开始我想到的是单调栈，单很快就发现这行不通。因为题目要求的并不是**下一个**比其大（或等于）的数，而是**下一个最小的**比其大（或等于）。

如果题目要求的是**下一个**比其大（或等于）的数。那么我可以写出如下的代码：

```py
n = len(A)
next_higher, next_lower = [-1] * n, [-1] * n

stack = []
for i, a in enumerate(A):
    while stack and A[stack[-1]] <= A[i]:
        next_higher[stack.pop()] = i
    stack.append(i)
stack = []
for i, a in enumerate(A):
    while stack and A[stack[-1]] >= A[i]:
        next_lower[stack.pop()] = i
    stack.append(i)
```

对上面代码不熟悉的朋友，可以看下我之前写的 [单调栈专题](/leetcode-solution/thinkings/monotone-stack.md)。

可是我们需要求的是**下一个最小的**比其大（或等于）呀。一种简单的方法是先对 A 进行排序再使用单调栈。比如我们进行升序排序，接下来只要遍历一次排好序的数组，同时结合单调栈即可。 由于已经进行了排序，因此后面的数一定是**不小于**前面的数的，且**对于任意相邻的数 a 和 b，a 的最小的大于等于它本身的数就是 b**，前提是 a 和 b 对应排序之前的索引 i 和 j 满足 i < j。这提示我们排序的时候需要额外记录原始索引。

代码：

```py
A = sorted([a, i] for i, a in enumerate(A))

```

这里有 1 个细节。即排序的时候如何处理相等情况，比如 a 和 b 相等，是保持之前的相对顺序还是逆序还是都可以？实际上，我们想希望的是保持之前的相对顺序，这样才不会错过相等的情况的解。因此我这里排序的是时候是以 \[a, i] 形式保存的数据。

由于除了要处理跳高，我们仍然需要处理跳低。而最关键的是跳低也需要我们**在 a 和 b 相等的情况下，保持之前的相对顺序**。 因此就不能通过简单的排序一次处理。比如我们不能这么干：

```py
class Solution:
    def oddEvenJumps(self, A):
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n
        A = sorted([a, i] for i, a in enumerate(A))

        stack = []
        for _, i in A:
            # it means stack[-1]'s next bigger(or equal) is i
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)

        stack = []
        for _, i in A[::-1]:
            # it means stack[-1]'s next smaller(or equal) is i
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)

        # ...
```

解决这个问题的方法最简单的莫过于使用两次排序，具体见下方代码区。

现在已经有了两个数组，这两个数组可以帮助我们

* **快速**找到下一个最小的比其大（或等于）的数。（奇数跳）
* **快速**找到下一个最大的比其小（或等于）的数。（偶数跳）

数据已经预处理完毕。接下来，只需要从结果倒推即可。这提示我们从后往前遍历。

算法：

* 使用前面的方法预处理出 next\_higher 和 next\_lower
* 使用两个数组 higher 和 lower。higher\[i] 表示是否可从 i 开始通过跳高的方式奇偶跳到达数组最后一项，lower 也是类似。
* 从后往前倒推遍历。如果 lower\[next\_higher\[i]] 为 true 说明 i 是可以通过跳高的方式奇偶跳到达数组最后一项的。higher\[next\_lower\[i]] 也是类似。
* 最后返回 higher 中 为 true 的个数。

### 代码

代码支持： Python3

Python Code:

```python
class Solution:
    def oddEvenJumps(self, A):
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        for _, i in sorted([a, i] for i, a in enumerate(A)):
            # it means stack[-1]'s next bigger(or equal) is i
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)

        stack = []
        for _, i in sorted([-a, i] for i, a in enumerate(A)):
            # it means stack[-1]'s next smaller(or equal) is i
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)

        higher, lower = [False] * n, [False] * n
        higher[-1] = lower[-1] = True
        ans = 1
        for i in range(n - 2, -1, -1):
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
            ans += higher[i]
        return ans

```

**复杂度分析**

令 N 为数组 A 的长度。

* 时间复杂度：$O(NlogN)$
* 空间复杂度：$O(N)$

有的同学好奇为什么不考虑 lower。类似：

```py
ans = 1
for i in range(n - 2, -1, -1):
    higher[i] = lower[next_higher[i]]
    lower[i] = higher[next_lower[i]]
    ans += higher[i] or lower[i]
return ans
```

根本原因是题目**要求我们必须从奇数跳开始**，而不是能偶数跳开始。如果题目不限制奇数跳和偶数跳，你可以自己自由选择的话，就必须使用上面的代码啦。

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/7qxoqa.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/975.odd-even-jump.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.