滑动窗口—中值问题
題目一：295. 數據流的中位數
問題描述：
中位數是有序列表中間的數。如果列表長度是偶數，中位數則是中間兩個數的平均值。例如，[2,3,4]?的中位數是 3、[2,3] 的中位數是 (2 + 3) / 2 = 2.5。設計一個支持以下兩種操作的數據結構：
- void addNum(int num) - 從數據流中添加一個整數到數據結構中。
- double findMedian() - 返回目前所有元素的中位數。
示例：
- addNum(1)
- addNum(2)
- findMedian() -> 1.5
- addNum(3)?
- findMedian() -> 2
進階：
- 如果數據流中所有整數都在 0 到 100 范圍內，你將如何優化你的算法？
- 如果數據流中 99% 的整數都在 0 到 100 范圍內，你將如何優化你的算法？
算法思路：
由于奇數長度和偶數長度的中位數定義不同，判斷「從數據流中讀出的數的個數的奇偶性」很重要，這是因為長度的奇偶性決定了中位數的個數。當從數據流中讀出的數的個數為奇數的時候，中位數只有 1 個；當從數據流中讀出的數的個數為偶數的時候，中位數有 2 個。我們不妨分別稱它們為「左中位數」和「右中位數」。
如果數據流中每讀出 1?個數后都排一次序，「中位數」就位于這些數的「中間」。「中位數」把它們分為兩個部分，一部分是「前有序數組」，另一部分是「后有序數組」。我們發現如下事實：
- 當從數據流中讀出的數的個數為奇數的時候，中位數是「前有序數組」中的最大值，如下左圖所示；
- 當從數據流中讀出的數的個數為偶數的時候，左中位數是「前有序數組」中的最大值，右中位數是「后有序數組」中的最小值，如下右圖所示。
由于我們只關心這兩個 有序數組 中的最值，有一個數據結構可以幫助我們快速找到這個最值，這就是 優先隊列 。具體來說：
- 前有序數組由于只關注最大值，可以 動態地 放置在一個最大堆中；
- 后有序數組由于只關注最小值，可以 動態地 放置在一個最小堆中。
- 當從數據流中讀出的數的個數為偶數的時候，我們想辦法讓兩個堆中的元素個數相等，兩個堆頂元素的平均值就是所求的中位數（如下左圖）；
- 當從數據流中讀出的數的個數為奇數的時候，我們想辦法讓最大堆的元素個數永遠比最小堆的元素個數多 11 個，那么最大堆的堆頂元素就是所求的中位數（如下右圖）。
為了得到所求的中位數，在任何時刻，兩個堆應該始終保持的性質如下：
- 最大堆的堆頂元素，小于或者等于最小堆的堆頂元素；
- 最大堆的元素個數或者與最小堆的元素個數相等，或者多 11 。
具體可以進行如下操作：
- 情況 1： 當兩個堆的元素個數之和為偶數（例如一開始的時候），為了讓最大堆中多 1 個元素，采用這樣的流程：「最大堆 → 最小堆 → 最大堆」；
- 情況 2： 當兩個堆的元素個數之和為奇數，此時最小堆必須多 11 個元素，這樣最大堆和最小堆的元素個數才相等，采用這樣的流程：「最大堆 → 最小堆」 即可。
因此無論兩個堆的元素個數之和是奇數或者是偶數，都得先「最大堆」 再「最小堆」 ，而當加入一個元素之后，元素個數為奇數的時候，再把最小堆的堆頂元素拿給最大堆就可以了。將元素放入優先隊列以后，優先隊列會自行調整（以對數時間復雜度），把最優值放入堆頂，是這道問題思路的關鍵。
總結：
腦子里建立如下動態的過程：為了找到添加新數據以后，數據流的中位數，我們讓新數據在最大堆和最小堆中都走了一遍。而為了讓最大堆的元素多 1 個，我們讓從最小堆中又拿出堆頂元素「送回」給最大堆；將元素放入優先隊列以后，優先隊列會以對數時間復雜度自行調整，把「最優值」調整到堆頂，這是使用優先隊列解決這個問題的原因。如果不太熟悉優先隊列的朋友們，請復習一下優先隊列的相關知識，包括基本操作、理解上浮和下沉。這道題使用 Java 編碼看起來思路更清晰一些，在 Python 中的堆只有最小堆，在構造最大堆的時候，要繞一個彎子，具體請看如下參考代碼。
上述文字出自：https://leetcode-cn.com/problems/find-median-from-data-stream/solution/you-xian-dui-lie-python-dai-ma-java-dai-ma-by-liwe/
參考代碼：
class MedianFinder {int count;PriorityQueue<Integer> maxHeap;PriorityQueue<Integer> minHeap;/** initialize your data structure here. */public MedianFinder() {count = 0;maxHeap = new PriorityQueue<>((x, y) -> y - x);minHeap = new PriorityQueue<>();}public void addNum(int num) {count += 1;maxHeap.offer(num);minHeap.offer(maxHeap.poll());if(count%2!=0)maxHeap.offer(minHeap.poll());}public double findMedian() {if(count%2!=0)return (double)maxHeap.peek();elsereturn (double)(maxHeap.peek()+minHeap.peek())/2;} }/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/復雜度分析：
時間復雜度：O(logN)，優先隊列的出隊入隊操作都是對數級別的，數據在兩個堆中間來回操作是常數級別的，綜上時間復雜度是 O(logN) 級別的；
空間復雜度：O(N)，使用了三個輔助空間，其中兩個堆的空間復雜度是O(?2N)，一個表示數據流元素個數的計數器 count，占用空間 O(1)，綜上空間復雜度為 O(N)。
題目二：480. 滑動窗口中位數
問題描述：
給你一個數組 nums，有一個長度為 k 的窗口從最左端滑動到最右端。窗口中有 k 個數，每次窗口向右移動 1 位。你的任務是找出每次窗口移動后得到的新窗口中元素的中位數，并輸出由它們組成的數組。
示例：
給出?nums = [1,3,-1,-3,5,3,6,7]，以及?k = 3，返回該滑動窗口的中位數數組?[1,-1,-1,3,5,6]。
窗口位置 ? ? ? ? ? ? ? ? ? ? ?中位數
--------------- ? ? ? ? ? ? ? -----
[1 ?3 ?-1] -3 ?5 ?3 ?6 ?7 ? ? ? 1
?1 [3 ?-1 ?-3] 5 ?3 ?6 ?7 ? ? ?-1
?1 ?3 [-1 ?-3 ?5] 3 ?6 ?7 ? ? ?-1
?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] ? ? ?6
算法思路：
本題考查動態維護數組的中位數。我們思考中位數的性質：如果一個數是中位數，那么在這個數組中，大于中位數的數目和小于中位數的數目，要么相等，要么就相差一。因此，我們采用對頂堆的做法，控制所有小于等于的數字放到一個堆中，控制所有比中位數大的數字放到另一個堆中，并且保證兩個堆的數目相差小于等于1。這樣就可以保證每一次查詢中位數的時候，答案一定出于兩個堆的堆頂元素之一。因此選定數據結構：優先隊列。因為優先隊列采用的是堆結構，正好符合我們的需求。我們將所有小于等于中位數的元素放到大頂堆，將所有大于中位數的元素放到小頂堆。
1）初始化方法如下：
- 將前K個元素全部插入到大頂堆中。從大頂堆中彈出K/2個元素到小頂堆中。
- 這樣，當K為奇數，則大頂堆元素比小頂堆元素多1；當K為偶數，兩個堆元素相等。
2）取中位數的操作：
- 我們的插入操作可以保證每次優先插入到大頂堆中，因此大頂堆中的元素個數大于等于小頂堆的元素個數。
- 當K為奇數時候，中位數是元素數量較多的大頂堆 堆頂元素。
- 當K為偶數時候，中位數是大頂堆和小頂堆的堆頂元素平均值。
3）窗口滑動過程中的操作：
- 假定在上一次滑動之后，已經有大頂堆和小頂堆元素數目相差小于等于1.
- 設置當前的滑動時，balance = 0。balance表示大頂堆元素數目減去小頂堆元素個數。
- 刪除窗口左側的元素：由于堆無法直接刪除掉某個指定元素，先欠下這個賬，等某次元素出現在堆頂的時候，再刪除他。mp記錄這個元素欠賬的個數。mp[left]++;雖然沒有真的在堆數據結構中刪除窗口最左側的元素，但是在我們的心中已經刪掉他了。堆兩側的平衡性發生了變化。如果left<=大頂堆.top()，就說明刪掉的元素在大頂堆中，我們讓balance--;否則，就說明刪掉的元素在小頂堆中，讓balance++;
- 添加進來窗口右側的元素。如果right<=大頂堆.top()，就應該讓這個元素放到samll堆里面，balance++；否則放到小頂堆里，balance--。
- 經過上面的操作，balance要么為0，要么為2，要么為-2。我們需要經過調整使得balance為0。
- 如果balance為0，在這次窗口滑動之前已經是平衡的，這次調整也沒有讓兩堆的數目變化，所以不用調整兩邊的堆。
- 如果balance為2，就說明small堆的元素比big堆的元素多了兩個。從small堆減少一個，big堆里增加一個，就可以讓兩邊相等。big.push(small.top());small.pop();
- 如果balance為-2，就說明big堆的元素比small堆的元素多了兩個。從big堆減少一個，small堆里增加一個，就可以讓兩邊相等。small.push(big.top());big.pop();
- 調整完了，現在該欠債還錢了。不能讓那些早該刪除的元素涉及到中位數的運算。
- 分別檢查兩邊的堆頂元素，如果堆頂元素欠著債，則彈出堆頂元素，直到堆頂元素沒有欠債為止。有朋友問了：堆頂下面也有欠債的怎么辦呢？我們之前說過，取中位數的時候只與堆頂元素有關，至于那些堆頂下面欠著債的，欠著就欠著吧，等他們到堆頂的時候再彈出去就好了。
- 最后，添加中位數即可。
上段文字出自：https://leetcode-cn.com/problems/sliding-window-median/solution/feng-xian-dui-chong-shuang-dui-dui-ding-hq1dt/
參考代碼：
class Solution {public double[] medianSlidingWindow(int[] nums, int k) {DualHeap dh = new DualHeap(k);for (int i = 0; i < k; ++i) {dh.insert(nums[i]);}double[] ans = new double[nums.length - k + 1];ans[0] = dh.getMedian();for (int i = k; i < nums.length; ++i) {dh.insert(nums[i]);dh.erase(nums[i - k]);ans[i - k + 1] = dh.getMedian();}return ans;} }class DualHeap {// 大根堆，維護較小的一半元素private PriorityQueue<Integer> small;// 小根堆，維護較大的一半元素private PriorityQueue<Integer> large;// 哈希表，記錄「延遲刪除」的元素，key 為元素，value 為需要刪除的次數private Map<Integer, Integer> delayed;private int k;// small 和 large 當前包含的元素個數，需要扣除被「延遲刪除」的元素private int smallSize, largeSize;public DualHeap(int k) {this.small = new PriorityQueue<Integer>(new Comparator<Integer>() {public int compare(Integer num1, Integer num2) {return num2.compareTo(num1);}});this.large = new PriorityQueue<Integer>(new Comparator<Integer>() {public int compare(Integer num1, Integer num2) {return num1.compareTo(num2);}});this.delayed = new HashMap<Integer, Integer>();this.k = k;this.smallSize = 0;this.largeSize = 0;}public double getMedian() {return (k & 1) == 1 ? small.peek() : ((double) small.peek() + large.peek()) / 2;}public void insert(int num) {if (small.isEmpty() || num <= small.peek()) {small.offer(num);++smallSize;} else {large.offer(num);++largeSize;}makeBalance();}public void erase(int num) {delayed.put(num, delayed.getOrDefault(num, 0) + 1);if (num <= small.peek()) {--smallSize;if (num == small.peek()) {prune(small);}} else {--largeSize;if (num == large.peek()) {prune(large);}}makeBalance();}// 不斷地彈出 heap 的堆頂元素，并且更新哈希表private void prune(PriorityQueue<Integer> heap) {while (!heap.isEmpty()) {int num = heap.peek();if (delayed.containsKey(num)) {delayed.put(num, delayed.get(num) - 1);if (delayed.get(num) == 0) {delayed.remove(num);}heap.poll();} else {break;}}}// 調整 small 和 large 中的元素個數，使得二者的元素個數滿足要求private void makeBalance() {if (smallSize > largeSize + 1) {// small 比 large 元素多 2 個large.offer(small.poll());--smallSize;++largeSize;// small 堆頂元素被移除，需要進行 pruneprune(small);} else if (smallSize < largeSize) {// large 比 small 元素多 1 個small.offer(large.poll());++smallSize;--largeSize;// large 堆頂元素被移除，需要進行 pruneprune(large);}} } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生總結
- 上一篇： Java集合—PriorityQueue
- 下一篇： JVM—学习路线