求讨论，Google OA题 奇偶跳 该怎么做？

题目如图。
我目前的想法（不一定对）：两个dp数组，存储从当前位置分别奇偶跳能否到达最后的位置。然后从后往前遍历数组，同时维护一个递增的list，每次用binary在递增数组里找比当前数字大/小的数。
请问是否正确？是否有更好的方法？

挺好的题。有一个小细节：Leetcode上的那道975题和楼上的有小区别，楼主的是等于大于；Leetcode是大于

我好像必须用了两个map来分别query奇数跳和偶数跳
    map<int, int> ascend;
    map<int, int, greater<int>> descend;

我觉得你的解法是可行的。

但是想问你"从后往前遍历数组，维护一个递增的list"是怎么维护呢？如果是从位置i走到位置(i - 1)的时候，把A[i]插入到这个递增的list的相应位置(就像insertion sort那样)，那么不管这个递增的list是ArrayList还是LinkedList，总的复杂度都是O(n^2)。因为ArrayList在插入的时候需要挪动O(n)个元素，LinkedList需要O(n)来找到插入的位置。

为了达到O(n logn)的时间复杂度，最好维护一个balanced binary tree而不是一个list。这样无论是query还是insert都是O(log n), 总的复杂度就是O(n log n)了。写C++的话可以用<map>的数据结构，Java里应该也有类似的吧。

补充内容 (2018-12-30 07:52):
这样的话这个解法就是O(n log n)的时间复杂度，O(n)的空间复杂度。暂时还不确定是不是有更好的。

补充内容 (2018-12-30 07:54):
格式有问题。"把A插入到这个递增的list"应该是"把A(i)插入到这个递增的list"。之前用的方括号，被论坛解读成斜体了，汗。

可以用dynamic programming。
从后往前，对于每个数记录两个boolean变量，分别是从这个数开始奇数跳和开始偶数跳能否到达最后一个数。假设当前的数是a，若是从a奇数跳到的是b，则从a开始奇数跳和从b开始偶数跳的boolean的值应该是一致的。最后算有多少数的奇数跳的boolean的值是true就行了。
求加米

我个人的想法：用DP， 从后往前扫描，因为前一次是奇数跳，那么下一次就是从新的位置进行偶数跳，这样就可以用之前的结果（分别是奇数次跳从这个位置开始，和偶数次这个位置开始起跳）（因为我们是从后往前扫描）。用一个map(红黑树)/treemap去储存后面扫描过的数字，每次去找到第一个大于当前位置的数字或者小于当前位置的数字（没有找到就是false）。这样dp就连接起来了。 时间复杂度应该是O(nlogn) 空间复杂度应该是O(n)。如果要用binary search的话你还是每次都需要sort一下已经扫描过的数字，因为原来的序列是无序的，用pq也没办法高效的insert或者访问节点。所以我感觉是用map来做比较合理。
希望大家一起讨论指正

会不会有重复的数字呢？

leetcode今天竞赛已经有这个题了~975 Odd Even Jump