# 0975. Odd Even Jump
###### tags: `Leetcode` `Hard` `Dynamic Programming` `TreeMap`
Link: https://leetcode.com/problems/odd-even-jump/description/
## 思路 $O(NlogN)$ $O(N)$
思路[参考](https://leetcode.com/problems/odd-even-jump/solutions/217981/java-c-python-dp-using-map-or-stack/)
需要一步higher 一步lower交替走
并且需要从higher开始
## Code

class Solution {
    public int oddEvenJumps(int[] arr) {
        int n = arr.length;
        boolean[] higher = new boolean[n];
        boolean[] lower = new boolean[n];
        higher[n-1] = true;
        lower[n-1] = true;
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(arr[n-1], n-1);
        int cnt = 1;
        for(int i=n-2; i>=0; i--){
            Integer floor = map.floorKey(arr[i]);
            if(floor!=null) lower[i] = higher[map.get(floor)];
            Integer ceil = map.ceilingKey(arr[i]);
            if(ceil!=null) higher[i] = lower[map.get(ceil)];
            if(higher[i]) cnt++;
            map.put(arr[i], i);
        }
        return cnt;
    }
}