【剑指 Offer(专项突击版)】057、059刷题笔记【滑动窗口+红黑树】【优先队列】

[057 - 剑指 Offer II 057. 值和下标之差都在给定的范围内【滑动窗口+红黑树】](https://leetcode-cn.com/problems/7WqeDu/)[059 - 剑指 Offer II 059. 数据流的第 K 大数值【优先队列】](https://leetcode-cn.com/problems/jBjn9C/)

用红黑树维护一个大小为k的滑动窗口。

对于每一个元素nums[i]，从窗口[max(i-k,0), i)中找到最接近nums[i]的数，这个数可能是

小于等于nums[i]的最大值left ;或大于等于nums[i]的最小值right。

如果存在这样的left或者right使得其与nums[i]的差小于等于t，即返回true。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet treeSet = new TreeSet<>();

        for (int i = 0; i < n; i++) {
            Long num = nums[i] * 1L;
            // 小于等于num的最大值
            Long left = treeSet.floor(num);
            // 大于等于num的最小值
            Long right = treeSet.ceiling(num);
            if (left != null && num - left <= t)
                return true;
            if (right != null && right - num <= t)
                return true;
            treeSet.add(num);
            if (i >= k) 
                treeSet.remove(nums[i - k] * 1L);
        }

        return false;
    }
}

用一个大小为k的优先队列来存储前k大的元素，其中优先队列的队头为队列中最小的元素。

初始化：将初始元素插入到优先队列中。插入：插入元素后，如果队列的大小大于k，则将队头元素（最小的）弹出。最后返回队头元素（第k大元素）。

class KthLargest {
    private PriorityQueue pq;
    int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        pq = new PriorityQueue<>();
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        pq.offer(val);
        if (pq.size() > k) {
            pq.poll(); // 弹出最小的
        }
        return pq.peek(); // 第K大
    }
}