優(yōu)先隊(duì)列（PriorityQueue）

優(yōu)先隊(duì)列也是隊(duì)列的一種账嚎，它的特點(diǎn)：

• 不像隊(duì)列按照先進(jìn)先出來(lái)的。優(yōu)先隊(duì)列是正常進(jìn)入察皇，按照優(yōu)先級(jí)出（優(yōu)先級(jí)是優(yōu)先隊(duì)列本身你可以設(shè)置的一個(gè)屬性蕉堰，優(yōu)先級(jí)可以是最大值先出，或者是元素的隊(duì)列里出現(xiàn)的次數(shù)最多的先出）

優(yōu)先隊(duì)列的實(shí)現(xiàn)機(jī)制（了解即可搁骑，不需要自己去實(shí)現(xiàn)）

• 堆（heap）實(shí)現(xiàn)（可以有很多種堆斧吐，比如：二叉堆、多項(xiàng)式堆仲器、斐波那契堆）

  
  
  常見(jiàn)堆.png

小頂堆（二叉堆的一種煤率，特點(diǎn)是父節(jié)點(diǎn)比左右孩子節(jié)點(diǎn)都要小，最小的元素永遠(yuǎn)在堆頂）

小頂堆.png

大頂堆（二叉堆的一種乏冀，特點(diǎn)是父節(jié)點(diǎn)比左右孩子節(jié)點(diǎn)都要大蝶糯，最大的元素永遠(yuǎn)在堆頂）

大頂堆.png

• 二叉搜索樹(shù)

push : 向棧中添加元素
peek : 返回棧頂元素
pop : 返回并刪除棧頂元素的操作

1.數(shù)據(jù)流中第K大元素（LeetCode - 703）

設(shè)計(jì)一個(gè)找到數(shù)據(jù)流中第K大元素的類(lèi)（class）。注意是排序后的第K大元素辆沦，不是第K個(gè)不同的元素昼捍。你的 KthLargest 類(lèi)需要一個(gè)同時(shí)接收整數(shù) k 和整數(shù)數(shù)組nums 的構(gòu)造器识虚，它包含數(shù)據(jù)流中的初始元素。每次調(diào)用 KthLargest.add妒茬，返回當(dāng)前數(shù)據(jù)流中第K大的元素担锤。你可以假設(shè) nums 的長(zhǎng)度≥ 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

方法一：第一次的時(shí)候從接受到的數(shù)組nums中取出前K大的數(shù)保存起來(lái)乍钻，以后每次add加入新的數(shù)據(jù)肛循，就將新數(shù)據(jù)和保存的前k大的數(shù)進(jìn)行排序丛塌，每次排序后都只保留K個(gè)數(shù)捏浊，將最小的淘汰掉菇存。用例子中K=3舉例就是第一次的時(shí)候保存前三大的數(shù)忆绰，也就是[4,5,8]与帆，添加進(jìn)來(lái)3之后將3和[4,5,8]排序疆瑰，3最小淘汰掉糕簿，保存的還是[4,5,8]屈扎，如果第二次進(jìn)來(lái)的10怀挠，將10和[4,5,8]排序析蝴，淘汰掉最小的4，保存下來(lái)的是[5,8,10]绿淋，然后返回保存下來(lái)的數(shù)據(jù)中的最小值就可以了闷畸。

這種方法的缺點(diǎn)是時(shí)間復(fù)雜度比較高：如果是N個(gè)數(shù)的話(huà)，時(shí)間復(fù)雜度是N*K*logK ,每次排序采用快排吞滞，時(shí)間復(fù)雜度是K*logK 佑菩，加上數(shù)據(jù)量是k，所以總的復(fù)雜度就是N*K*logK

方法二：采用優(yōu)先隊(duì)列裁赠，維護(hù)一個(gè)小頂堆（Min Heap）,因?yàn)槲覀円业贙大的元素殿漠，所以要保證小頂堆中元素個(gè)數(shù)始終是K個(gè)。在小頂堆中佩捞，堆頂元素是最小元素绞幌，那么每次有新元素進(jìn)來(lái)只需要和堆頂元素比較大小，如果新元素比堆頂元素小直接舍棄一忱，維持原來(lái)的堆不變莲蜘。新元素比堆頂元素大的話(huà)，舍棄堆頂元素帘营，將新元素加入小頂堆中票渠，小頂堆會(huì)重新更新，維持堆頂元素最小的特點(diǎn)芬迄。我們要找第K大元素的話(huà)问顷，只要返回小頂堆的堆頂元素就可以了。

這種方法的時(shí)間復(fù)雜度是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();
    }
} 

滑動(dòng)窗口最大值（LeetCode - 239）

給定一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)杜窄。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字肠骆。滑動(dòng)窗口每次只向右移動(dòng)一位羞芍。返回滑動(dòng)窗口中的最大值哗戈。你可以假設(shè)k 總是有效的，在輸入數(shù)組不為空的情況下荷科，1 ≤ k ≤ 輸入數(shù)組的大小唯咬。

例如：

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7] 
解釋: 

  滑動(dòng)窗口的位置                最大值
---------------               -----
[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

方法一：最簡(jiǎn)單直接的方法是遍歷每個(gè)滑動(dòng)窗口，找到每個(gè)窗口的最大值畏浆。一共有 N - k + 1 個(gè)滑動(dòng)窗口胆胰，每個(gè)有 k 個(gè)元素，于是算法的時(shí)間復(fù)雜度為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;
    }
}

• 時(shí)間復(fù)雜度：O(N*k)。其中 N 為數(shù)組中元素個(gè)數(shù)蝎毡。
• 空間復(fù)雜度：O(N?k+1)厚柳，用于輸出數(shù)組。

方法二：因?yàn)槊看味家页龃翱谥械淖畲笤劂灞晕覀兛梢允褂么箜敹眩∕ax Heap）的優(yōu)先隊(duì)列别垮，堆中元素個(gè)數(shù)是K，要找的最大元素就是堆頂元素扎谎。在這個(gè)大頂堆中碳想，我們還要記錄元素的索引，每次窗口移動(dòng)的操作就是將堆中前面的元素移出去毁靶，后面新的元素加入進(jìn)來(lái)胧奔，然后返回堆頂元素。這種方法的時(shí)間復(fù)雜度是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++) {
            // 刪除隊(duì)列中小于窗口左邊下標(biāo)的元素
            if(i >= k && i - k + 1 > deque.peek()) deque.remove();
            
            // 從隊(duì)列右側(cè)開(kāi)始, 刪除小于nums[i] 的元素
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
                deque.removeLast();
            
            deque.add(i);
            
            // 隊(duì)列左側(cè)是最大值,加入結(jié)果
            if(i - k + 1 >= 0)
                res[i - k + 1] = nums[deque.peek()];
        }
        return res;
}

方法三：我們可以使用雙向隊(duì)列预吆，該數(shù)據(jù)結(jié)構(gòu)可以從兩端以常數(shù)時(shí)間壓入/彈出元素龙填。存儲(chǔ)雙向隊(duì)列的索引比存儲(chǔ)元素更方便，因?yàn)閮烧叨寄茉跀?shù)組解析中使用拐叉。步驟如下：

1.處理前 k 個(gè)元素觅够，初始化雙向隊(duì)列。

2.遍歷整個(gè)數(shù)組巷嚣。在每一步 ，清理雙向隊(duì)列 :

• 只保留當(dāng)前滑動(dòng)窗口中有的元素的索引钳吟。
• 移除比當(dāng)前元素小的所有元素廷粒，它們不可能是最大的。

3.將當(dāng)前元素添加到雙向隊(duì)列中。

4.將 deque[0] 添加到輸出中坝茎。

5.返回輸出數(shù)組

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();
      
    // 移除掉雙向隊(duì)列中比當(dāng)前元素小的所有元素
    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;

    //初始化雙向隊(duì)列和輸出數(shù)組
    this.nums = nums;
    int max_idx = 0;
    for (int i = 0; i < k; i++) {
      clean_deque(i, k);
      deq.addLast(i);
      //計(jì)算前K個(gè)數(shù)中最大元素的索引
      if (nums[i] > nums[max_idx]) max_idx = i;
    }
    int [] output = new int[n - k + 1];
    //得到第一次K個(gè)數(shù)中的最大值涤姊，保存在output[0]中
    output[0] = nums[max_idx];

    //遍歷數(shù)組中從k到n-1個(gè)元素，得到每次滑動(dòng)窗口的最大值
    for (int i  = k; i < n; i++) {
      clean_deque(i, k);
      deq.addLast(i);
      output[i - k + 1] = nums[deq.getFirst()];
    }
    return output;
  }
}

• 時(shí)間復(fù)雜度：O(N)嗤放，每個(gè)元素被處理兩次 -- 分別是其索引被添加到雙向隊(duì)列中和被雙向隊(duì)列刪除思喊。

• 空間復(fù)雜度：O(N)，輸出數(shù)組使用了 O(N?k+1) 空間次酌，雙向隊(duì)列使用了O(k)恨课。

方法四: 動(dòng)態(tài)規(guī)劃，本算法的優(yōu)點(diǎn)是不需要使用 數(shù)組 / 列表 之外的任何數(shù)據(jù)結(jié)構(gòu)岳服。

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;
  }
}

• 時(shí)間復(fù)雜度：O(N)剂公，我們對(duì)長(zhǎng)度為 N 的數(shù)組處理了 3次。

• 空間復(fù)雜度：O(N)吊宋，用于存儲(chǔ)長(zhǎng)度為 N 的 left 和 right 數(shù)組纲辽，以及長(zhǎng)度為 N - k + 1的輸出數(shù)組。