奇偶跳

难度: Hard

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

Submission

运行时间: 90 ms

内存: 19.3 MB

from collections import deque

class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        N = len(arr)

        def make(A:List[int]) -> List[int]:
            made = [None] * N # 若made[k]为None则表示从索引k开始进行奇/偶跳无法找到下一个符合题意要求的位置
            MONO_STACK = list() # 存储原数组arr从小到大的值对应的索引
            for idx in A:
                while MONO_STACK and idx > MONO_STACK[-1]:
                    made[MONO_STACK.pop()] = idx
                MONO_STACK.append(idx)
            return made

        A = sorted(range(N), key=lambda id: arr[id])
        nexto:List[int] = make(A)
        A.sort(key=lambda id: -arr[id])
        nexte:List[int] = make(A)

        # (双状态)布尔状态机动态规划
        Odp = [False] * N; Odp[-1] = True
        Edp = [False] * N; Edp[-1] = True
        for idx in range(N-1, -1, -1):
            if nexto[idx] is not None: # 原数组索引为idx的位置可以进行奇数跳，跳到索引为nexto[idx]的位置
                Odp[idx] = Edp[nexto[idx]]
            if nexte[idx] is not None:
                Edp[idx] = Odp[nexte[idx]]
        # 为True的位置就是满足题意的个数
        return sum(Odp)

Explain

本题解采用动态规划与单调栈的结合来解决奇偶跳的问题。首先，为了找到每个位置的奇数跳和偶数跳的目的地，我们使用单调栈两次：一次处理奇数跳，一次处理偶数跳。奇数跳需要找到右边第一个不小于当前值的最小值，而偶数跳需要找到右边第一个不大于当前值的最大值。这可以通过对数组的索引排序，并以此顺序遍历数组，使用单调栈完成。之后，使用动态规划自后向前计算，对于每个位置，记录其奇数跳和偶数跳是否能到达数组的末尾。最后，统计可以通过奇数跳到达末尾的起始位置数量，即为答案。

时间复杂度: O(N log N)

空间复杂度: O(N)

from collections import deque

class Solution:
    def oddEvenJumps(self, arr: List[int]) -> int:
        N = len(arr)

        def make(A:List[int]) -> List[int]:
            made = [None] * N
            MONO_STACK = list()
            for idx in A:
                while MONO_STACK and idx > MONO_STACK[-1]:
                    made[MONO_STACK.pop()] = idx
                MONO_STACK.append(idx)
            return made

        A = sorted(range(N), key=lambda id: arr[id])
        nexto:List[int] = make(A)
        A.sort(key=lambda id: -arr[id])
        nexte:List[int] = make(A)

        Odp = [False] * N; Odp[-1] = True
        Edp = [False] * N; Edp[-1] = True
        for idx in range(N-1, -1, -1):
            if nexto[idx] is not None:
                Odp[idx] = Edp[nexto[idx]]
            if nexte[idx] is not None:
                Edp[idx] = Odp[nexte[idx]]
        return sum(Odp)

Explore

在处理奇数跳时，我们需要找到右边第一个不小于当前元素的最小元素，这可以通过将数组索引按照元素值的升序排序来实现。这样，当我们遍历排序后的索引时，能保证每一个新遍历到的元素都不小于之前的元素。使用单调栈来维护一个从栈底到栈顶递减的元素顺序，可以保证每次弹出栈顶元素时，找到的是右边第一个不小于它的元素。对于偶数跳，需要找到右边第一个不大于当前元素的最大元素，因此按照元素值的降序排序索引，使用同样的单调栈策略，可以有效找到满足条件的元素。

在函数`make`中使用单调栈来维护一个索引的序列，这些索引代表的元素从栈底到栈顶是按照一定的顺序（奇数跳为递减，偶数跳为递增）排列的。当当前索引`idx`大于栈顶元素时（对于奇数跳来说，意味着我们找到了一个右边的、不小于栈顶元素并且是最接近的一个），我们需要进行弹栈操作，将栈顶元素对应的下一个可跳至的索引设置为当前索引`idx`。这确保了每个元素都能找到其合适的跳跃目的地。

`Odp`数组用于存储从每个位置出发，通过奇数次跳跃是否能够到达数组末尾的布尔值。`Edp`数组则存储通过偶数次跳跃是否能到达数组末尾的布尔值。在动态规划的过程中，我们从数组的末尾向前计算，对于每个位置，如果其奇数跳的目的地存在，则`Odp`的值取决于该目的地通过偶数跳能否到达末尾（即`Edp[nexto[idx]]`）。同理，`Edp`的值则取决于其偶数跳的目的地通过奇数跳能否到达末尾（即`Odp[nexte[idx]]`）。这种交互确保了从任一位置出发的跳跃路径的可行性可以被正确计算。

在这个问题中，动态规划是从数组的末尾向前计算的。这是因为每个位置是否能够通过奇偶跳到达末尾取决于其后面的位置的状态。具体地，对于每个位置`idx`，如果存在奇数跳的目的地`nexto[idx]`，则`Odp[idx]`的值将取决于在`nexto[idx]`通过偶数跳是否能到达末尾的状态（即`Edp[nexto[idx]]`）。同样，如果存在偶数跳的目的地`nexte[idx]`，则`Edp[idx]`的值将取决于在`nexte[idx]`通过奇数跳是否能到达末尾的状态（即`Odp[nexte[idx]]`）。这种从后向前的更新保证了每一个位置的状态都是基于其后续位置的正确状态计算得出的，从而确保整体计算的正确性。