优先队列(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的输出数组。
网友评论