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)
可是我们需要求的是下一个最小的比其大（或等于）呀。一种简单的方法是先对 A 进行排序再使用单调栈。比如我们进行升序排序，接下来只要遍历一次排好序的数组，同时结合单调栈即可。 由于已经进行了排序，因此后面的数一定是不小于前面的数的，且对于任意相邻的数 a 和 b，a 的最小的大于等于它本身的数就是 b，前提是 a 和 b 对应排序之前的索引 i 和 j 满足 i < j。这提示我们排序的时候需要额外记录原始索引。
代码：
A = sorted([a, i] for i, a in enumerate(A))
这里有 1 个细节。即排序的时候如何处理相等情况，比如 a 和 b 相等，是保持之前的相对顺序还是逆序还是都可以？实际上，我们想希望的是保持之前的相对顺序，这样才不会错过相等的情况的解。因此我这里排序的是时候是以 [a, i] 形式保存的数据。
由于除了要处理跳高，我们仍然需要处理跳低。而最关键的是跳低也需要我们在 a 和 b 相等的情况下，保持之前的相对顺序。 因此就不能通过简单的排序一次处理。比如我们不能这么干：
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:
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。类似：
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
