K Empty Slots

题目

答案和分析
这题花了一点时间想思路
第一步非常重要，对于这种稍微复杂的题目你要先想出最简单的方法，然后思考这个方法的瓶颈在于哪里，如果去提高它

对于这题最简单的做法如下

对于每个position，check 它和position - k - 1或position + k + 1之间的k个position此时有没有种花
复杂度是O(nk)，k是因为我们需要check中间的k个position是否有种花
如何将k降低为log级别呢
我们可以用一个tree记录所有当前的position
打个比方
你现在在某position，你想知道position和position + k + 1之间有没有种花，只需查看对应position的node的right child是否为position + k + 1即可

本来写出这么个solution

public class Solution {
    TreeNode root = null;
    Map<Integer, TreeNode> map = new HashMap<>();

    public TreeNode insert(TreeNode root, TreeNode node) {
        if(root == null) return node;
        else if(root.val > node.val) {
            // Go left
            root.left = insert(root.left, node);
        }
        else {
            root.right = insert(root.right, node);
        }
        return root;
    }

    public boolean check(TreeNode root, int left, int right, int target) {
        if(root == null) return false;
        if(root.val > left && root.val < right) return true;
        if(root.val > target) return check(root.left, left, right, target);
        else return check(root.right, left, right, target);
    }
    public int kEmptySlots(int[] flowers, int k) {
        for(int i = 0; i < flowers.length; i++) {
            int curr_pos = flowers[i];
            int prev_k_pos = curr_pos - k - 1;
            int next_k_pos = curr_pos + k + 1;

            TreeNode newnode = new TreeNode(curr_pos);
            this.root = insert(root, newnode);
            map.put(curr_pos, newnode);

            TreeNode curr_node = map.get(curr_pos);
            TreeNode prev_k_node = map.get(prev_k_pos);
            TreeNode next_k_node = map.get(next_k_pos);

            if(prev_k_node != null) {
                // Check path from prev_k_node.right to curr_node for number in range(prev_k_pos, curr_pos)
                // Check path from curr_node.left to prev_k_node for number in range(prev_k_pos, curr_pos)
                if(!check(prev_k_node, prev_k_pos, curr_pos, curr_pos)) return i + 1;
                if(!check(curr_node, prev_k_pos, curr_pos, prev_k_pos)) return i + 1;

            }
            if(next_k_node != null) {
                // Check path from curr_node.right to next_k_node for number in range(prev_k_pos, curr_pos)
                // Check path from next_k_node.left to curr_node for number in range(prev_k_pos, curr_pos)
                if(!check(curr_node, curr_pos, next_k_pos, next_k_pos)) return i + 1;
                if(!check(next_k_node, curr_pos, next_k_pos, curr_pos)) return i + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] flowers = new int[]{6,5,8,9,7,1,10,2,3,4};
        int k = 2;
        System.out.println(sol.kEmptySlots(flowers, k));
    }

}

但是check 两个position之间种花的部分总是不对，跟我想象中不一样，最后只能用java的Treeset的lower和higher函数来解决了

class Solution {
    TreeSet<Integer> tree = new TreeSet<>();

    public int kEmptySlots(int[] flowers, int k) {
        for(int i = 0; i < flowers.length; i++) {
            int curr_pos = flowers[i];
            int prev_k_pos = curr_pos - k - 1;
            int next_k_pos = curr_pos + k + 1;

            tree.add(curr_pos);
            Integer l = tree.lower(curr_pos);
            Integer r = tree.higher(curr_pos);
            if((l != null && l == prev_k_pos) || (r != null && r == next_k_pos)) return i + 1;
        }
        return -1;
    }
}