红黑树的Java实现TreeSet及相关LeetCode题目

关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers

红黑树是一种自平衡的二叉排序树，实现原理参见 教你透彻了解红黑树

Java 中的 TreeSet 使用红黑树实现。提供了一些比较实用的方法：

• add(E e)
• contains(Object o)
• first()
  • Returns the first (lowest) element currently in this set. 返回最小值
• last()
  • Returns the last (highest) element currently in this set. 返回最大值
• higher(E e)
  • Returns the least element in this set strictly greater than the given element, or null if there is no such element. 返回大于e的元素
• ceiling(E e)
  • Returns the least element in this set greater than or equal to the given element, or null if there is no such element. 返回大于或者等于e的元素
• tailSet(E fromElement)
  • Returns a view of the portion of this set whose elements are greater than or equal to fromElement. 返回大于或者等于e的所有元素
• lower(E e)
  • Returns the greatest element in this set strictly less than the given element, or null if there is no such element. 返回小于e的元素
• floor(E e)
  • Returns the greatest element in this set less than or equal to the given element, or null if there is no such element. 返回小于或者等于e的元素
• headSet(E toElement)
  • Returns a view of the portion of this set whose elements are strictly less than toElement. 返回小于e的所有元素

LeetCode题目：683 K Empty Slots
There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn't such day, output -1.

Example 1:

Input:
flowers: [1,3,2]
k: 1
Output: 2

Explanation: In the second day, the first and the third flower have become blooming.

Example 2:

Input:
flowers: [1,2,3]
k: 1
Output: -1

class Solution {
    public int kEmptySlots(int[] flowers, int k) {
        // 使用红黑树，查询效率 O(logN)
        TreeSet<Integer> set = new TreeSet<>();
        
        for(int i = 0; i < flowers.length; i++) {
            // 找到离该花最近的两个花
            Integer lower = set.lower(flowers[i]);
            Integer higher = set.higher(flowers[i]);
            
            set.add(flowers[i]);
            
            if(lower != null && (flowers[i] - lower - 1) == k) return i + 1;
            
            if(higher != null && (higher - flowers[i] - 1) == k) return i + 1;
        }
        
        return -1;
    }
}