滑动窗口—中值问题
題目一：295. 數(shù)據(jù)流的中位數(shù)
問題描述：
中位數(shù)是有序列表中間的數(shù)。如果列表長度是偶數(shù)，中位數(shù)則是中間兩個(gè)數(shù)的平均值。例如，[2,3,4]?的中位數(shù)是 3、[2,3] 的中位數(shù)是 (2 + 3) / 2 = 2.5。設(shè)計(jì)一個(gè)支持以下兩種操作的數(shù)據(jù)結(jié)構(gòu)：
- void addNum(int num) - 從數(shù)據(jù)流中添加一個(gè)整數(shù)到數(shù)據(jù)結(jié)構(gòu)中。
- double findMedian() - 返回目前所有元素的中位數(shù)。
示例：
- addNum(1)
- addNum(2)
- findMedian() -> 1.5
- addNum(3)?
- findMedian() -> 2
進(jìn)階：
- 如果數(shù)據(jù)流中所有整數(shù)都在 0 到 100 范圍內(nèi)，你將如何優(yōu)化你的算法？
- 如果數(shù)據(jù)流中 99% 的整數(shù)都在 0 到 100 范圍內(nèi)，你將如何優(yōu)化你的算法？
算法思路：
由于奇數(shù)長度和偶數(shù)長度的中位數(shù)定義不同，判斷「從數(shù)據(jù)流中讀出的數(shù)的個(gè)數(shù)的奇偶性」很重要，這是因?yàn)殚L度的奇偶性決定了中位數(shù)的個(gè)數(shù)。當(dāng)從數(shù)據(jù)流中讀出的數(shù)的個(gè)數(shù)為奇數(shù)的時(shí)候，中位數(shù)只有 1 個(gè)；當(dāng)從數(shù)據(jù)流中讀出的數(shù)的個(gè)數(shù)為偶數(shù)的時(shí)候，中位數(shù)有 2 個(gè)。我們不妨分別稱它們?yōu)椤缸笾形粩?shù)」和「右中位數(shù)」。
如果數(shù)據(jù)流中每讀出 1?個(gè)數(shù)后都排一次序，「中位數(shù)」就位于這些數(shù)的「中間」。「中位數(shù)」把它們分為兩個(gè)部分，一部分是「前有序數(shù)組」，另一部分是「后有序數(shù)組」。我們發(fā)現(xiàn)如下事實(shí)：
- 當(dāng)從數(shù)據(jù)流中讀出的數(shù)的個(gè)數(shù)為奇數(shù)的時(shí)候，中位數(shù)是「前有序數(shù)組」中的最大值，如下左圖所示；
- 當(dāng)從數(shù)據(jù)流中讀出的數(shù)的個(gè)數(shù)為偶數(shù)的時(shí)候，左中位數(shù)是「前有序數(shù)組」中的最大值，右中位數(shù)是「后有序數(shù)組」中的最小值，如下右圖所示。
由于我們只關(guān)心這兩個(gè) 有序數(shù)組 中的最值，有一個(gè)數(shù)據(jù)結(jié)構(gòu)可以幫助我們快速找到這個(gè)最值，這就是 優(yōu)先隊(duì)列 。具體來說：
- 前有序數(shù)組由于只關(guān)注最大值，可以 動(dòng)態(tài)地 放置在一個(gè)最大堆中；
- 后有序數(shù)組由于只關(guān)注最小值，可以 動(dòng)態(tài)地 放置在一個(gè)最小堆中。
- 當(dāng)從數(shù)據(jù)流中讀出的數(shù)的個(gè)數(shù)為偶數(shù)的時(shí)候，我們想辦法讓兩個(gè)堆中的元素個(gè)數(shù)相等，兩個(gè)堆頂元素的平均值就是所求的中位數(shù)（如下左圖）；
- 當(dāng)從數(shù)據(jù)流中讀出的數(shù)的個(gè)數(shù)為奇數(shù)的時(shí)候，我們想辦法讓最大堆的元素個(gè)數(shù)永遠(yuǎn)比最小堆的元素個(gè)數(shù)多 11 個(gè)，那么最大堆的堆頂元素就是所求的中位數(shù)（如下右圖）。
為了得到所求的中位數(shù)，在任何時(shí)刻，兩個(gè)堆應(yīng)該始終保持的性質(zhì)如下：
- 最大堆的堆頂元素，小于或者等于最小堆的堆頂元素；
- 最大堆的元素個(gè)數(shù)或者與最小堆的元素個(gè)數(shù)相等，或者多 11 。
具體可以進(jìn)行如下操作：
- 情況 1： 當(dāng)兩個(gè)堆的元素個(gè)數(shù)之和為偶數(shù)（例如一開始的時(shí)候），為了讓最大堆中多 1 個(gè)元素，采用這樣的流程：「最大堆 → 最小堆 → 最大堆」；
- 情況 2： 當(dāng)兩個(gè)堆的元素個(gè)數(shù)之和為奇數(shù)，此時(shí)最小堆必須多 11 個(gè)元素，這樣最大堆和最小堆的元素個(gè)數(shù)才相等，采用這樣的流程：「最大堆 → 最小堆」 即可。
因此無論兩個(gè)堆的元素個(gè)數(shù)之和是奇數(shù)或者是偶數(shù)，都得先「最大堆」 再「最小堆」 ，而當(dāng)加入一個(gè)元素之后，元素個(gè)數(shù)為奇數(shù)的時(shí)候，再把最小堆的堆頂元素拿給最大堆就可以了。將元素放入優(yōu)先隊(duì)列以后，優(yōu)先隊(duì)列會(huì)自行調(diào)整（以對數(shù)時(shí)間復(fù)雜度），把最優(yōu)值放入堆頂，是這道問題思路的關(guān)鍵。
總結(jié)：
腦子里建立如下動(dòng)態(tài)的過程：為了找到添加新數(shù)據(jù)以后，數(shù)據(jù)流的中位數(shù)，我們讓新數(shù)據(jù)在最大堆和最小堆中都走了一遍。而為了讓最大堆的元素多 1 個(gè)，我們讓從最小堆中又拿出堆頂元素「送回」給最大堆；將元素放入優(yōu)先隊(duì)列以后，優(yōu)先隊(duì)列會(huì)以對數(shù)時(shí)間復(fù)雜度自行調(diào)整，把「最優(yōu)值」調(diào)整到堆頂，這是使用優(yōu)先隊(duì)列解決這個(gè)問題的原因。如果不太熟悉優(yōu)先隊(duì)列的朋友們，請復(fù)習(xí)一下優(yōu)先隊(duì)列的相關(guān)知識，包括基本操作、理解上浮和下沉。這道題使用 Java 編碼看起來思路更清晰一些，在 Python 中的堆只有最小堆，在構(gòu)造最大堆的時(shí)候，要繞一個(gè)彎子，具體請看如下參考代碼。
上述文字出自：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();*/復(fù)雜度分析：
時(shí)間復(fù)雜度：O(logN)，優(yōu)先隊(duì)列的出隊(duì)入隊(duì)操作都是對數(shù)級別的，數(shù)據(jù)在兩個(gè)堆中間來回操作是常數(shù)級別的，綜上時(shí)間復(fù)雜度是 O(logN) 級別的；
空間復(fù)雜度：O(N)，使用了三個(gè)輔助空間，其中兩個(gè)堆的空間復(fù)雜度是O(?2N)，一個(gè)表示數(shù)據(jù)流元素個(gè)數(shù)的計(jì)數(shù)器 count，占用空間 O(1)，綜上空間復(fù)雜度為 O(N)。
題目二：480. 滑動(dòng)窗口中位數(shù)
問題描述：
給你一個(gè)數(shù)組 nums，有一個(gè)長度為 k 的窗口從最左端滑動(dòng)到最右端。窗口中有 k 個(gè)數(shù)，每次窗口向右移動(dòng) 1 位。你的任務(wù)是找出每次窗口移動(dòng)后得到的新窗口中元素的中位數(shù)，并輸出由它們組成的數(shù)組。
示例：
給出?nums = [1,3,-1,-3,5,3,6,7]，以及?k = 3，返回該滑動(dòng)窗口的中位數(shù)數(shù)組?[1,-1,-1,3,5,6]。
窗口位置 ? ? ? ? ? ? ? ? ? ? ?中位數(shù)
--------------- ? ? ? ? ? ? ? -----
[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
算法思路：
本題考查動(dòng)態(tài)維護(hù)數(shù)組的中位數(shù)。我們思考中位數(shù)的性質(zhì)：如果一個(gè)數(shù)是中位數(shù)，那么在這個(gè)數(shù)組中，大于中位數(shù)的數(shù)目和小于中位數(shù)的數(shù)目，要么相等，要么就相差一。因此，我們采用對頂堆的做法，控制所有小于等于的數(shù)字放到一個(gè)堆中，控制所有比中位數(shù)大的數(shù)字放到另一個(gè)堆中，并且保證兩個(gè)堆的數(shù)目相差小于等于1。這樣就可以保證每一次查詢中位數(shù)的時(shí)候，答案一定出于兩個(gè)堆的堆頂元素之一。因此選定數(shù)據(jù)結(jié)構(gòu)：優(yōu)先隊(duì)列。因?yàn)閮?yōu)先隊(duì)列采用的是堆結(jié)構(gòu)，正好符合我們的需求。我們將所有小于等于中位數(shù)的元素放到大頂堆，將所有大于中位數(shù)的元素放到小頂堆。
1）初始化方法如下：
- 將前K個(gè)元素全部插入到大頂堆中。從大頂堆中彈出K/2個(gè)元素到小頂堆中。
- 這樣，當(dāng)K為奇數(shù)，則大頂堆元素比小頂堆元素多1；當(dāng)K為偶數(shù)，兩個(gè)堆元素相等。
2）取中位數(shù)的操作：
- 我們的插入操作可以保證每次優(yōu)先插入到大頂堆中，因此大頂堆中的元素個(gè)數(shù)大于等于小頂堆的元素個(gè)數(shù)。
- 當(dāng)K為奇數(shù)時(shí)候，中位數(shù)是元素?cái)?shù)量較多的大頂堆 堆頂元素。
- 當(dāng)K為偶數(shù)時(shí)候，中位數(shù)是大頂堆和小頂堆的堆頂元素平均值。
3）窗口滑動(dòng)過程中的操作：
- 假定在上一次滑動(dòng)之后，已經(jīng)有大頂堆和小頂堆元素?cái)?shù)目相差小于等于1.
- 設(shè)置當(dāng)前的滑動(dòng)時(shí)，balance = 0。balance表示大頂堆元素?cái)?shù)目減去小頂堆元素個(gè)數(shù)。
- 刪除窗口左側(cè)的元素：由于堆無法直接刪除掉某個(gè)指定元素，先欠下這個(gè)賬，等某次元素出現(xiàn)在堆頂?shù)臅r(shí)候，再刪除他。mp記錄這個(gè)元素欠賬的個(gè)數(shù)。mp[left]++;雖然沒有真的在堆數(shù)據(jù)結(jié)構(gòu)中刪除窗口最左側(cè)的元素，但是在我們的心中已經(jīng)刪掉他了。堆兩側(cè)的平衡性發(fā)生了變化。如果left<=大頂堆.top()，就說明刪掉的元素在大頂堆中，我們讓balance--;否則，就說明刪掉的元素在小頂堆中，讓balance++;
- 添加進(jìn)來窗口右側(cè)的元素。如果right<=大頂堆.top()，就應(yīng)該讓這個(gè)元素放到samll堆里面，balance++；否則放到小頂堆里，balance--。
- 經(jīng)過上面的操作，balance要么為0，要么為2，要么為-2。我們需要經(jīng)過調(diào)整使得balance為0。
- 如果balance為0，在這次窗口滑動(dòng)之前已經(jīng)是平衡的，這次調(diào)整也沒有讓兩堆的數(shù)目變化，所以不用調(diào)整兩邊的堆。
- 如果balance為2，就說明small堆的元素比big堆的元素多了兩個(gè)。從small堆減少一個(gè)，big堆里增加一個(gè)，就可以讓兩邊相等。big.push(small.top());small.pop();
- 如果balance為-2，就說明big堆的元素比small堆的元素多了兩個(gè)。從big堆減少一個(gè)，small堆里增加一個(gè)，就可以讓兩邊相等。small.push(big.top());big.pop();
- 調(diào)整完了，現(xiàn)在該欠債還錢了。不能讓那些早該刪除的元素涉及到中位數(shù)的運(yùn)算。
- 分別檢查兩邊的堆頂元素，如果堆頂元素欠著債，則彈出堆頂元素，直到堆頂元素沒有欠債為止。有朋友問了：堆頂下面也有欠債的怎么辦呢？我們之前說過，取中位數(shù)的時(shí)候只與堆頂元素有關(guān)，至于那些堆頂下面欠著債的，欠著就欠著吧，等他們到堆頂?shù)臅r(shí)候再彈出去就好了。
- 最后，添加中位數(shù)即可。
上段文字出自：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 {// 大根堆，維護(hù)較小的一半元素private PriorityQueue<Integer> small;// 小根堆，維護(hù)較大的一半元素private PriorityQueue<Integer> large;// 哈希表，記錄「延遲刪除」的元素，key 為元素，value 為需要?jiǎng)h除的次數(shù)private Map<Integer, Integer> delayed;private int k;// small 和 large 當(dāng)前包含的元素個(gè)數(shù)，需要扣除被「延遲刪除」的元素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;}}}// 調(diào)整 small 和 large 中的元素個(gè)數(shù)，使得二者的元素個(gè)數(shù)滿足要求private void makeBalance() {if (smallSize > largeSize + 1) {// small 比 large 元素多 2 個(gè)large.offer(small.poll());--smallSize;++largeSize;// small 堆頂元素被移除，需要進(jìn)行 pruneprune(small);} else if (smallSize < largeSize) {// large 比 small 元素多 1 個(gè)small.offer(large.poll());++smallSize;--largeSize;// large 堆頂元素被移除，需要進(jìn)行 pruneprune(large);}} } 超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生總結(jié)
- 上一篇： Java集合—PriorityQueue
- 下一篇： JVM—学习路线