美文网首页
算法通关 - 优先队列

算法通关 - 优先队列

作者: angeliur | 来源:发表于2020-02-25 20:06 被阅读0次
    优先队列(PriorityQueue)

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

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

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

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


      常见堆.png

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


    小顶堆.png

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


    大顶堆.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.haomeiwen.com/subject/wbnfchtx.html