当前位置: 首页>后端>正文

算法通关 - 优先队列

优先队列(PriorityQueue)

优先队列也是队列的一种,它的特点:

  • 不像队列按照先进先出来的。优先队列是正常进入,按照优先级出(优先级是优先队列本身你可以设置的一个属性,优先级可以是最大值先出,或者是元素的队列里出现的次数最多的先出)

优先队列的实现机制(了解即可,不需要自己去实现)

  • 堆(heap)实现(可以有很多种堆,比如:二叉堆、多项式堆、斐波那契堆)


    算法通关 - 优先队列,第1张
    常见堆.png

小顶堆(二叉堆的一种,特点是父节点比左右孩子节点都要小,最小的元素永远在堆顶)


算法通关 - 优先队列,第2张
小顶堆.png

大顶堆(二叉堆的一种,特点是父节点比左右孩子节点都要大,最大的元素永远在堆顶)


算法通关 - 优先队列,第3张
大顶堆.png
  • 二叉搜索树

push : 向栈中添加元素
peek : 返回栈顶元素
pop : 返回并删除栈顶元素的操作

1.数据流中第K大元素(LeetCode - 703)

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第K大的元素。你可以假设 nums 的长度≥ k-1k ≥ 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的输出数组。

https://www.xamrdz.com/backend/3ym1925906.html

相关文章: