975. Odd Even Jump

Version #1 TreeMap
题目提示很强的treemap
tricky 的地方在于treemap不能处理duplicate key
所以从后往前扫

100.00 %
class Solution {
    public int oddEvenJumps(int[] A) {
        int len = A.length;
        boolean[] dpOdd = new boolean[len];
        boolean[] dpEven = new boolean[len];
        dpOdd[len - 1] = true;
        dpEven[len - 1] = true;
        // key-> A[j], value-> index
        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(A[len - 1], len - 1);
        for (int i = len - 2; i >= 0; i--) {
            int currKey = A[i];
            // assume curr is odd->
            Map.Entry<Integer, Integer> nextCeil = map.ceilingEntry(currKey);
            if (nextCeil == null) {
                dpOdd[i] = false;
            } else {
                dpOdd[i] = dpEven[nextCeil.getValue()];
            }
            Map.Entry<Integer, Integer> nextFloor = map.floorEntry(currKey);
            if (nextFloor == null) {
                dpEven[i] = false;
            } else {
                dpEven[i] = dpOdd[nextFloor.getValue()];
            }
            map.put(currKey, i);
        }
        int result = 0;
        for (int i = 0; i < len; i++) {
            if (dpOdd[i]) result++;
        }
        return result;
    }
}