C ++中的奇数偶跳
现在我们可以以这种方式从索引i向前跳到索引j（i<j）-
在奇数跳转中，我们可以跳转到索引j，使得A[i]<=A[j]并且A[j]是最小的可能值。当有多个这样的索引j时，我们只能跳到最小的这样的索引j。
在偶数跳转中，我们可以跳转到索引j，以使A[i]>=A[j]且A[j]为最大可能值。当有多个这样的索引j时，我们只能跳到最小的这样的索引j。
对于某些索引i，可能会没有合法的跳跃。
现在，从该索引开始，我们可以通过跳跃一些次数到达数组的末尾，因此将其称为好索引。
我们必须找到良好的起始索引的数量。
因此，如果输入像[10,13,12,14,15]，则输出将为2，因为从末尾可以到达的地方有两个位置索引3和4。
为了解决这个问题，我们将遵循以下步骤-
ret：=1
n：=A的大小
定义一个nextNextEqual大小为n的数组，用-1填充
定义一个数组nextSmallerEqual大小为n用-1填充
定义一个映射st
对于初始化i：=n-1，当i>=0时，更新（将i减1），-
（增加1）
if：=值不大于A[i]的键值对
nextGreaterEqual[i]：=如果(it)不是最后一个元素，则为它的值，否则为-1
如果它不等于st的最后一个元素，并且第一个元素与A[i]相同，则-
nextSmallerEqual[i]：=如果(it)不是第一个元素，则为前一个元素的值，否则为-1
st[A[i]]：=i
定义一个大小为nx2的2D数组v并用false填充它
v[n-1，0]=v[n-1，1]=true
对于初始化i：=n-2，当i>=0时，更新（将i减1），执行-
（增加ret1）
v[i，0]：=v[nextSmallerEqual[i]，1]
v[i，1]：=v[nextGreaterEqual[i]，0]
如果nextGreaterEqual[i]不等于-1，则-
如果nextSmallerEqual[i]不等于-1，则-
如果v[i，1]不为零，则-
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int oddEvenJumps(vector<int>& A){
int ret = 1;
int n = A.size();
vector<int> nextGreaterEqual(n, -1);
vector<int> nextSmallerEqual(n, -1);
map<int, int> st;
for (int i = n - 1; i >= 0; i--) {
map<int, int>::iterator it = st.lower_bound(A[i]);
nextGreaterEqual[i] = (it != st.end()) ? it->second : -1;
if (it != st.end() && it->first == A[i])
it++;
nextSmallerEqual[i] = it != st.begin() ? prev(it)->second
: -1;
st[A[i]] = i;
}
vector<vector<bool> > v(n, vector<bool>(2, false));
v[n - 1][0] = v[n - 1][1] = true;
for (int i = n - 2; i >= 0; i--) {
if (nextGreaterEqual[i] != -1) {
v[i][1] = v[nextGreaterEqual[i]][0];
}
if (nextSmallerEqual[i] != -1) {
v[i][0] = v[nextSmallerEqual[i]][1];
}
if (v[i][1])
ret++;
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {10,13,12,14,15};
cout << (ob.oddEvenJumps(v));
}输入值
{10,13,12,14,15}输出结果
2