算法通关 - 优先队列
优先队列（PriorityQueue）
优先队列也是队列的一种，它的特点：
- 不像队列按照先进先出来的。优先队列是正常进入，按照优先级出（优先级是优先队列本身你可以设置的一个属性，优先级可以是最大值先出，或者是元素的队列里出现的次数最多的先出）
优先队列的实现机制（了解即可，不需要自己去实现）
-
堆（heap）实现（可以有很多种堆，比如：二叉堆、多项式堆、斐波那契堆）
常见堆.png
小顶堆（二叉堆的一种，特点是父节点比左右孩子节点都要小，最小的元素永远在堆顶）
小顶堆.png
大顶堆（二叉堆的一种，特点是父节点比左右孩子节点都要大，最大的元素永远在堆顶）
大顶堆.png
- 二叉搜索树
push : 向栈中添加元素
peek : 返回栈顶元素
pop : 返回并删除栈顶元素的操作
1.数据流中第K大元素（LeetCode - 703）
设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。你可以假设 nums 的长度≥ k-1 且k ≥ 1。
如下所示：
链接：https://leetcode-cn.com/problems/kth-largest-element-in-a-stream
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
方法一：第一次的时候从接受到的数组nums中取出前K大的数保存起来，以后每次add加入新的数据，就将新数据和保存的前k大的数进行排序，每次排序后都只保留K个数，将最小的淘汰掉。用例子中K=3举例就是第一次的时候保存前三大的数，也就是[4,5,8]，添加进来3之后将3和[4,5,8]排序，3最小淘汰掉，保存的还是[4,5,8]，如果第二次进来的10，将10和[4,5,8]排序，淘汰掉最小的4，保存下来的是[5,8,10]，然后返回保存下来的数据中的最小值就可以了。
这种方法的缺点是时间复杂度比较高：如果是N个数的话，时间复杂度是N*K*logK ,每次排序采用快排，时间复杂度是K*logK ，加上数据量是k，所以总的复杂度就是N*K*logK
方法二：采用优先队列，维护一个小顶堆（Min Heap）,因为我们要找第K大的元素，所以要保证小顶堆中元素个数始终是K个。在小顶堆中，堆顶元素是最小元素，那么每次有新元素进来只需要和堆顶元素比较大小，如果新元素比堆顶元素小直接舍弃，维持原来的堆不变。新元素比堆顶元素大的话，舍弃堆顶元素，将新元素加入小顶堆中，小顶堆会重新更新，维持堆顶元素最小的特点。我们要找第K大元素的话，只要返回小顶堆的堆顶元素就可以了。
这种方法的时间复杂度是N*log₂K
class KthLargest {
PriorityQueue<Integer> q;
int k;
public KthLargest(int k, int[] nums) {
this.k = k;
q = new PriorityQueue<>(k);
for(int n : nums){
add(n);
}
}
public int add(int val) {
if(q.size() < k){
q.offer(val);
}else if(q.peek() < val){
q.poll();
q.offer(val);
}
return q.peek();
}
}
滑动窗口最大值（LeetCode - 239）
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。你可以假设k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
例如：
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
方法一：最简单直接的方法是遍历每个滑动窗口，找到每个窗口的最大值。一共有 N - k + 1 个滑动窗口，每个有 k 个元素，于是算法的时间复杂度为O(N*k)，性能较差。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
int [] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) {
int max = Integer.MIN_VALUE;
for(int j = i; j < i + k; j++)
max = Math.max(max, nums[j]);
output[i] = max;
}
return output;
}
}
- 时间复杂度：O(N*k)。其中
N为数组中元素个数。 - 空间复杂度：O(N−k+1)，用于输出数组。
方法二：因为每次都要找出窗口中的最大元素，所以我们可以使用大顶堆（Max Heap）的优先队列，堆中元素个数是K，要找的最大元素就是堆顶元素。在这个大顶堆中，我们还要记录元素的索引，每次窗口移动的操作就是将堆中前面的元素移出去，后面新的元素加入进来，然后返回堆顶元素。这种方法的时间复杂度是N*logK
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length==0) return new int[0];
int[] res = new int[nums.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for(int i=0;i<nums.length;i++) {
// 删除队列中小于窗口左边下标的元素
if(i >= k && i - k + 1 > deque.peek()) deque.remove();
// 从队列右侧开始, 删除小于nums[i] 的元素
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
deque.removeLast();
deque.add(i);
// 队列左侧是最大值,加入结果
if(i - k + 1 >= 0)
res[i - k + 1] = nums[deque.peek()];
}
return res;
}
方法三：我们可以使用双向队列，该数据结构可以从两端以常数时间压入/弹出元素。存储双向队列的索引比存储元素更方便，因为两者都能在数组解析中使用。步骤如下：
1.处理前 k 个元素，初始化双向队列。
2.遍历整个数组。在每一步 ，清理双向队列 :
- 只保留当前滑动窗口中有的元素的索引。
- 移除比当前元素小的所有元素，它们不可能是最大的。
3.将当前元素添加到双向队列中。
4.将 deque[0] 添加到输出中。
5.返回输出数组
class Solution {
ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
int [] nums;
public void clean_deque(int i, int k) {
if (!deq.isEmpty() && deq.getFirst() == i - k)
deq.removeFirst();
// 移除掉双向队列中比当前元素小的所有元素
while (!deq.isEmpty() && nums[i] > nums[deq.getLast()]) deq.removeLast();
}
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
if (k == 1) return nums;
//初始化双向队列和输出数组
this.nums = nums;
int max_idx = 0;
for (int i = 0; i < k; i++) {
clean_deque(i, k);
deq.addLast(i);
//计算前K个数中最大元素的索引
if (nums[i] > nums[max_idx]) max_idx = i;
}
int [] output = new int[n - k + 1];
//得到第一次K个数中的最大值，保存在output[0]中
output[0] = nums[max_idx];
//遍历数组中从k到n-1个元素，得到每次滑动窗口的最大值
for (int i = k; i < n; i++) {
clean_deque(i, k);
deq.addLast(i);
output[i - k + 1] = nums[deq.getFirst()];
}
return output;
}
}
- 时间复杂度：O(N)，每个元素被处理两次 -- 分别是其索引被添加到双向队列中和被双向队列删除。
- 空间复杂度：O(N)，输出数组使用了 O(N−k+1) 空间，双向队列使用了O(k)。
方法四: 动态规划，本算法的优点是不需要使用 数组 / 列表 之外的任何数据结构。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
if (k == 1) return nums;
int [] left = new int[n];
left[0] = nums[0];
int [] right = new int[n];
right[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
// from left to right
if (i % k == 0) left[i] = nums[i]; // block_start
else left[i] = Math.max(left[i - 1], nums[i]);
// from right to left
int j = n - i - 1;
if ((j + 1) % k == 0) right[j] = nums[j]; // block_end
else right[j] = Math.max(right[j + 1], nums[j]);
}
int [] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++)
output[i] = Math.max(left[i + k - 1], right[i]);
return output;
}
}
- 时间复杂度：O(N)，我们对长度为 N 的数组处理了 3次。
- 空间复杂度：O(N)，用于存储长度为 N 的 left 和 right 数组，以及长度为 N - k + 1的输出数组。
