题目描述
给定一个整数数组 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），那么该索引就会被认为是好的起始索引。
返回好的起始索引的数量。
样例
输入：[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,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）出发，通过一定数量的跳跃到达数组末尾。
输入：[5,1,3,4,2]
输出：3
解释：
我们可以从起始索引 1，2，4 出发到达数组末尾。
注意
1 <= A.length <= 200000 <= A[i] < 100000
算法
(单调栈，记忆化搜索) $O(n \log n)$
- 假设我们已经有了一个算法能快速的得到下一次要跳的位置，此时可以直接用一次记忆化搜索得到答案。具体为，用数组
f[i][flag]表示当前在第i个位置，flag == 0表示第奇数次跳，flag == 1表示第偶数次跳，能否到达终点。利用dp(i, flag)递归，用数组f[i][flag]进行记忆化。 - 现在我们需要找到这样的算法得到下一次要跳的位置。在每一次跳动的过程中，我们需要找到坐标大于
i中，大于（小于）等于当前A[i]的最小（大）的那个数的下标j。 - 我们先考虑找到坐标大于
i中，大于等于当前A[i]的最小的那个数的下标j。首先求出当前数组的argsort和rank。argsort指的是A[argsort[i]]是一个有序的数组。rank是A数组每个数字的排名。如果有重复数字，则下标小的数字更小。我们发现，在argsort数组中，我们仅需要找到右边第一个比当前数字大的位置right[i]，这个位置就对应我们在奇数次跳跃时的目标。这一步可以利用单调栈来解决，单调栈的过程此处不在赘述（有很多相关题解）。下一次要跳的位置可以具体化如下，假设rank[i]就是对应argsort数组中的某个下标x，找到y = right[x]，然后argsort[y]就是数组A中对应的下标。这一步请读者自行拿笔和纸验证。 - 同理，找到坐标大于
i中，小于等于当前A[i]的最大的那个数的下标j时也要利用单调栈，但是，需要重新构造argsort和rank数组，使得 如果有重复数字，则下标小的数字更大。因为在后续单调栈找左边第一个比当前数字大，如果还按照之前的argsort和rank，则会发生找到的是跳到满足要求的最大索引j上（可以拿笔和纸验证），故这里需要两组argsort和rank。
时间复杂度
- 记忆化搜索的时间复杂度为 $O(n)$，排序的时间复杂度为 $O(n \log n)$，单调栈的总时间复杂度为 $O(n)$，所以整个算法的时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要记忆化数组，argsort，rank 和单调栈的空间，故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
vector<vector<int>> f;
vector<int> argsort1, rank1, argsort2, rank2;
vector<int> left, right;
int dp(int x, int flag, const vector<int>& A) {
if (f[x][flag] != -1)
return f[x][flag];
int n = A.size();
if (x == n - 1)
return f[x][flag] = 1;
if (flag == 0) {
if (right[rank1[x]] == n)
return f[x][flag] = 0;
return f[x][flag] = dp(argsort1[right[rank1[x]]], 1 - flag, A);
}
else {
if (left[rank2[x]] == -1)
return f[x][flag] = 0;
return f[x][flag] = dp(argsort2[left[rank2[x]]], 1 - flag, A);
}
}
int oddEvenJumps(vector<int>& A) {
int n = A.size(), ans = 0;
stack<int> st;
vector<pair<int, int>> A1, A2;
for (int i = 0; i < n; i++) {
A1.emplace_back(make_pair(A[i], i));
A2.emplace_back(make_pair(A[i], n - i - 1));
}
sort(A1.begin(), A1.end());
sort(A2.begin(), A2.end());
argsort1.resize(n);
argsort2.resize(n);
rank1.resize(n);
rank2.resize(n);
for (int i = 0; i < n; i++) {
argsort1[i] = A1[i].second;
rank1[i] = lower_bound(A1.begin(), A1.end(), make_pair(A[i], i)) - A1.begin();
argsort2[i] = n - A2[i].second - 1;
rank2[i] = lower_bound(A2.begin(), A2.end(), make_pair(A[i], n - i - 1)) - A2.begin();
}
right.resize(n);
for (int i = 0; i < n; i++) {
while (!st.empty() && argsort1[st.top()] < argsort1[i]) {
right[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
right[st.top()] = n;
st.pop();
}
/*********************************************/
left.resize(n);
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && argsort2[st.top()] < argsort2[i]) {
left[st.top()] = i;
st.pop();
}
st.push(i);
}
while (!st.empty()) {
left[st.top()] = -1;
st.pop();
}
f.resize(n, vector<int>(2, -1));
for (int i = 0; i < n; i++)
if (dp(i, 0, A) == 1)
ans++;
return ans;
}
};
相似的模块化实现。