975. Odd even jump

思路

1. 从后向前遍历
2. 分别用两个flag, can_higher[i]和can_lower[i]存储从节点i能否继续跳到更高（>=）点或者更低（<=）点
3. 重点：使用treemap存储已经访问过的点以简化查找

复杂度

• 时间：
• 空间：

代码

class Solution {
public:
    int oddEvenJumps(vector<int>& A) {
        int n = A.size();
        int res = 1;

        vector<int> can_higher(n, 0), can_lower(n, 0);
        can_higher[n - 1] = can_lower[n - 1] = 1;

        map<int, int> tree;
        tree[A.back()] = n - 1;

        for(int i = n - 2; i >= 0; i--){
            int cur = A[i];
            auto first_larger = tree.upper_bound(cur);
            auto first_not_smaller = tree.lower_bound(cur);

            // if can go higher, means first_not_smaller exist
            if(first_not_smaller != tree.end())
                can_higher[i] = can_lower[first_not_smaller->second];

            // if can go lower, means first_not_larger exist
            // which means first_larger is not the beginning of the tree
            if(first_larger != tree.begin())
                can_lower[i] = can_higher[(--first_larger)->second];

            // each start is a odd jump, which means it should go higher
            if (can_higher[i])
                res++;
            tree[cur] = i;
        }
        return res;
    }
};