【九章算法强化班】堆Heap&双端队列Dequeue

堆

基本性质

• 支持操作：Add $O(logN)$/Remove$O(logN)$/Min or Max$O(1)$

• heap可以用来求最大值或者最小值，不能同时求最大和最小值。

• Heap结构：

  一颗尽量填满的二叉树，每次插入节点时，插到最后一行的最左端的空余位置，如果本层没有空余位置了，另起一行。因此节点数目为N的堆对应的二叉树高度为$O(logN)$

• MaxHeap vs MinHeap

  • MaxHeap：父亲节点比左右孩子都大
  • MinHeap：父亲节点比左右孩子都小

  因此当取最大或最小时，将root值取出即可，因此getMin/Max的时间复杂度为$O(1)$

• 堆的存储

  由于我们需要频繁的对堆进行增加删除，所以一般堆的底层都是通过数组来实现（而不能用链表，因为链表需要频繁new 或 delete对象，非常慢）

  对于元素A[i]：

  • 父节点：A[i-2/2] (右移1)
  • 左孩子：A[2i+1] (左移1，可得到2i)
  • 右孩子：A[2i+2] (左移1，低位+1，可得到2i+1)

• 插入操作

  例子：在最小堆中插入元素：
  	1
    ↙  ↘
   2		3
  插入0，因为第二行已经满了，加入到第三行最左边：
  	1
    ↙  ↘
   2		3
  ↙
  0
  此时这个堆已经不满足最小堆的条件（父亲节点都比孩子小）了，因此，先交换0和2：
  	1
    ↙  ↘
   0		3
  ↙
  2
  此时仍然不满足最小堆条件，继续交换：
  	0
    ↙  ↘
   1		3
  ↙
  2
  此时满足最小堆条件了，因此，需要交换最多 O(logN)次，插入的时间复杂度为O(logN)

  ​

• 删除操作

  例子：在最小堆中删除元素：
       	 1
      ↙  		↘
     3			2
   ↙  ↘       ↙  	↘
  4      5	 10		100
  删除堆顶元素1，用堆中最后一个节点替换堆顶元素：
       	100
      ↙  		↘
     3			2
   ↙  ↘       ↙  	
  4      5	 10		
  此时这个堆已经不满足最小堆的条件（父亲节点都比孩子小）了，因此将堆顶元素下沉，选择左右孩子中较小的交换：
       	 2
      ↙  		↘
     3		  100
   ↙  ↘       ↙  	
  4      5	 10	
  此时仍然不满足最小堆条件，继续交换：
       	 2
      ↙  		↘
     3		  10
   ↙  ↘       ↙  	
  4      5	 100	
  
  好了，删好了

  PriorityQueue支持$O(logN)$ 删除堆顶元素，但对于删除除root外的任意一点的操作，PriorityQueue的时间复杂度会降到$O(N)$

  Java中还有另外一种数据结构TreeMap，支持$O(logN)$ 删除任意元素，而且支持同时获取最大和最小。

  TreeMap是一平衡二叉搜索树，因此插入和删除任意元素的时间复杂度都是$O(logN)$

  | | 用 | 原理 | 实现 |
  | ——————- | —— | —————- | —— |
  | TreeMap | 必会 | 平衡二叉搜索树，红黑树 | 不需要 |
  | PriorityQueue | 必会 | heap，二叉树 | 选做 |

实现

构建堆，堆维护

上面提到了增加和删除节点的操作，下面通过实例说明如何从一个数组开始构建一个堆：

假设我们有数组4,1,3,2,16,9,10,14,8,7

它的形状为：

当然最暴力的方式就是从最后一个元素【7】开始，向上以此对树进行维护。但事实上由于后[n/2]个元素都是根节点，不需要进行维护。因此我们只需要维护前[n/2]个节点。

具体步骤如下图所示：

伪代码为：

BUILD-MAX-HEAP(A)
	A.heap.size = A.length
	for i = [A.length/2] downto 1
      MAX-HEAPIFTY(A,i)

根据上面的方法，我们可以将一个数组构建成一个堆，堆顶的元素是最大的。

代码：

public class MyHeap {
    private int[] A;
    private int heapSize;

    //构造函数
    MyHeap(int[] a){
        this.A = a;
        heapSize = a.length;
    }
    //交换堆中元素
    public void swap(int i,int j){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }

    //堆维护（最大堆）
    public void heapify(int i){
        //计算左孩子和右孩子在数组中的坐标。
        int leftChild = 2*i+1;
        int rightChild = 2*i+2;

        //找到左右孩子和该节点本身中最大的
        int largest = -1;
        if(leftChild < heapSize && A[i] < A[leftChild]){//如果有左孩子而且左孩子比父亲大
            largest = leftChild;
        }
        else {
            largest = i;
        }
        if(rightChild < heapSize && A[largest] < A[rightChild]){//如果有右孩子而且左孩子比当前最大的大
            largest = rightChild;
        }

        if(largest!= i){//如果最大的不是该节点，是其孩子，则需要交换，维护
            swap(i,largest);
            heapify(largest);
        }
    }

    //构建最大堆
    public void build(){
        for(int i = (heapSize-2)/2;i>=0;i--){
            heapify(i);
        }
    }

    public static void main(String[] args){
        int[] nums = {2,8,1,5,6,3,4};
        MyHeap test = new MyHeap(nums);
        test.build();
        for(int i : nums){
            System.out.print(i);
        }
    }
}

时间复杂度分析:

在高度为h的结点上运行MAX-HEAPIFY的代价是O(h)O(h)，因此建树的总代价为：

$$\sum_{h=0}^{lgn}O(h)=O(n\sum_{h=0}^{lgn}\frac{h}{2^h})=O(n)$$

因此堆排序的时间复杂度为$O(n)$

删除节点POP

//删除节点
public int Poll(){
    int top = A[0];
    swap(0, heapSize-1);//交换第一个和最后一个节点
    heapSize--;
    heapify(0);//shiftdown 维护
    return top;
}

插入节点

//插入之后向上shift
public void shiftUp(int i){
    int parentID = (i-1)/2;
    if(parentID > -1){
        if(A[i] > A[parentID]){
            swap(i,parentID);
            shiftUp(parentID);
        }
    }
}

//插入节点
public void Add(int i){
    A[heapSize] = i;
    heapSize++;
    shiftUp(heapSize);
}

堆排序

堆排序就是利用堆的性质，依次将堆顶元素出堆，每次堆顶元素出堆之后堆会自动维护，所以可以保证弹出的节点是有序的。

//堆排序
public int[] HeapSort(){
    int[] res = new int[heapSize];
    int i = 0;
    int size = heapSize;
    while(i < size){
        res[i] = Poll();//堆顶元素出堆
        i++;
    }
    return res;
}

时间复杂度：$O(nlogn)$

n次出堆，每次出堆维护时间logn

HashHeap

哈希堆，Hashheap是用一个hashMap优化了的heap，方便快速定位某个值在heap中的位置。与heap相比，HashHeap多了一个用来指示元素位置的索引。

HashHeap的结构有点特殊，很神奇，需要多看几遍，其中包括两个结构heap和hashmap:

1. heap存储元素的值
2. HashMap存储元素在heap中对应的位置和出现的次数

这里存储出现次数是因为，有些时候，堆中可能会有重复的元素，如果只存储其位置的话，某个值就会在多个位置上，需要用一个链表来存储所有的位置，这样不仅存储起来不方便，计算也很不方便，所以很巧妙地，我们将同一个值的元素都放到heap中的同一个位置，在hashmap中存储该位置有多少个该元素，这样堆中的每个节点元素的值也不相同了，各种计算操作起来也方便了，完美~

java实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.function.BinaryOperator;

//hashheap实现，以最大堆为例
public class HashHeap {
    HashMap<Integer,Node> map;//存储元素值和在堆中的索引
    ArrayList<Integer> heap;
    int heapSize;
    boolean isMaxHeap;

    class Node{
        int idx;//节点在堆中的位置
        int count;//该数值出现次数
        Node(int idx,int count){
            this.idx = idx;
            this.count = count;
        }
    }

    public boolean isEmpty(){
        if(heapSize == 0){
            return true;
        }
        else return false;
    }

    HashHeap(boolean isMaxHeap){
        this.map = new HashMap<>();
        this.heap = new ArrayList<>();
        this.isMaxHeap = isMaxHeap;
        this.heapSize = 0;
    }


    //由数组构建最大堆
    public void Build(int[] nums){
        int counter = 0;
        for(int i : nums){
            System.out.println(counter);
            add(i);
            counter ++;
        }
    }

    //交换堆中节点
    public void swap(int i,int j){
        //获取ij在堆中指向的元素值
        int vali = heap.get(i);
        int valj = heap.get(j);

        //获取两个值在map中的个数
        int counti = map.get(vali).count;
        int countj = map.get(valj).count;

        //修改hashmap，把两个值对应的位置互换，count不变
        map.put(vali,new Node(j,counti));
        map.put(valj,new Node(i,countj));

        //交换堆中的节点值
        heap.set(i,valj);
        heap.set(j,vali);
    }

    //向上交换
    public void ShiftUp(int idx){
        int parentIdx = (idx-1)/2;
        if(parentIdx > -1 && idx < heapSize){
            //如果是最大堆而且孩子>父亲 || 是最小堆而且孩子<父亲,需要向上shift
            if((isMaxHeap && heap.get(parentIdx) < heap.get(idx)) ||
                   !isMaxHeap && heap.get(parentIdx) > heap.get(idx) ){
                swap(idx,parentIdx);
                ShiftUp(parentIdx);
            }
        }
    }

    //向下交换
    public void ShiftDown(int idx){
        int leftChildIdx = 2 * idx+1;
        int rightChildIdx = 2 * idx+2;
        int largestIdx = idx;
        if(leftChildIdx < heapSize){
            //如果是最大堆而且父亲节点小于孩子
            if((isMaxHeap && heap.get(idx) < heap.get(leftChildIdx)) ||
                    (!isMaxHeap && heap.get(idx) > heap.get(leftChildIdx))){
                largestIdx = leftChildIdx;
            }
        }

        if(rightChildIdx < heapSize){
            if((isMaxHeap && heap.get(largestIdx) < heap.get(rightChildIdx)) ||
                    (!isMaxHeap && heap.get(largestIdx) > heap.get(rightChildIdx))){
                largestIdx = rightChildIdx;
            }
        }
        if(largestIdx != idx){
            swap(idx,largestIdx);
            ShiftDown(largestIdx);
        }
    }

    //插入元素，值为n
    public void add(int n){
        //如果堆中已经有该元素了,放在原来的位置，heap不用动，map计数+1
        if(map.containsKey(n)){
            map.put(n,new Node(map.get(n).idx,map.get(n).count+1));
        }
        //如果堆中没有该元素
        else {
            map.put(n,new Node(heapSize,1));
            heap.add(n);
            heapSize++;
            ShiftUp(heapSize-1);
        }
    }
    //删除节点
    public void remove(int n){
        int idx = map.get(n).idx;
        int count = map.get(n).count;
        //如果该值的节点只有一个
        if(count == 1){
            swap(idx,heapSize-1);
            map.remove(n);///在map中删除
            heap.remove(heap.size()-1);
            heapSize--;
            ShiftUp(idx);
            ShiftDown(idx);//交换之后需要向下维护
        }
        //如果该值的节点有多个，heap不用动，map里count-1
        else {
            map.put(n, new Node(idx, count - 1));
        }
    }

    //弹出节点
    public int poll(){
        int peakVal = heap.get(0);
        int idx = map.get(peakVal).idx;
        int count = map.get(peakVal).count;
        //如果堆中只有一个该节点,需要与最后一个交换后维护，
        if(count == 1){
            //与最后一个交换
            swap(0,heapSize-1);
            heap.remove(heap.size()-1);
            heapSize--;
            ShiftDown(0);
            map.remove(peakVal);//在map中删除
        }
        //如果堆中有多个，heap不用变，map中对应count--；
        else {
            map.put(peakVal,new Node(idx,count-1));
        }
        return peakVal;
    }

    //获取堆顶元素
    public int peek(){
        return heap.get(0);
    }

    //堆排序
    public List<Integer> HeapSort() {
        List<Integer> res = new ArrayList<>();
        int size = heapSize;
        int i = 0;
        while (i < size){
            res.add(poll());
            i++;
        }
        return res;
    }

    public static void main(String[] args){
        HashHeap test = new HashHeap(true);
        int[] nums = {855249355,67860114,4098019,948907207,69865427,347655258,886401366,446677701,502269373};//int[] nums = {-2147483648,-2147483648,2147483647,-2147483648,-2147483648,-2147483648,2147483647,2147483647,2147483647,2147483647,-2147483648,2147483647,-2147483648};
        test.Build(nums);
        test.add(8);
        test.remove(3);
        List<Integer> res = test.HeapSort();
        System.out.print(res);
    }
}

leetcode 相关习题

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

向柱子中灌水，求能够灌水的总量。

分析

可以从边缘向内灌水，灌水的高度不会超过边缘柱子的高度的最小值，所以说：边缘高度奠定了灌水的基调

从低的一边（高度为h）向内灌水，能够灌水的量为（h-h_temp），遇到更高的柱子时，更新边缘。

显然，这是一个双指针问题。

开始时，令总水量sum=0，双指针指向边缘，左选择较小的向内移动，假如选择左边指针。

sum += 1，指针继续向右移动

此时左边指针遇到了跟高的边缘，右边指针开始向内移动

右边指针也同样遇到了更高的柱子，此时再从左右两边指针中选择一个较小的向内移动，假如选的依然是左边的，向内移动，更新sum，知道遇到更高的柱子

右侧指针左移，直到两指针相遇。

代码

public int trap(int[] height) {
    int left = 0;
    int right = height.length-1;
    int sum = 0;
    while(left < right){
        if(height[left]<height[right]){
            int min = height[left];
            left++;
            while(height[left]<=min && left < right){
                sum+=min-height[left];
                left++;
            }
        }
        else{
            int min = height[right];
            right--;
            while(height[right]<=min && left < right){
                sum+=min-height[right];
                right--;
            }
        }
    }
    return sum;
}

Trapping Rain Water II

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

Example:

> Given the following 3x6 height map:
> [
>   [1,4,3,1,3,2],
>   [3,2,1,3,2,4],
>   [2,3,3,2,3,1]
> ]
>
> Return 4.
>
>

>

The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.

After the rain, water are trapped between the blocks. The total volume of water trapped is 4.

分析

这一题是上一题在二维空间上的扩展。

对比上一题的思路，上一题的围墙是左右两边的柱子，而这道题的围墙是矩阵四周一圈的墙。我们可以从最矮的墙头向内灌水，然后将被灌水的位置加入围墙。

有两个要解决的点：

1. 找到围墙中最矮的墙头
2. 从最矮的墙头向围墙内灌水，要知道那边是围墙“内”

对于第1点，要求围墙中最矮的墙头，且墙头是动态插入的，可以维护一个最小堆，每次出堆元素即为最小的。

对于第2点，可以额外维护一个标记数组，记录是否已经被访问过，每次入堆就将该点对应的位置标记，若某一点没有被标记则是在围墙内。

以上图为例：

首先将四周设为围墙，将围墙元素入堆[1,4,3,1,3,2,3,4,2,3,3,2,3,1]

选取围墙中最小的，向内灌水，比如：

由于3>1，不能灌水，将3所在位置加入围墙[1,4,3,1,3,2,3,4,2,3,3,2,3,1, 3]

然后依次选取高度为1的其他几个围墙作为最矮的围墙，发现都不能够往里灌水，接下来选择高度为2的围墙，发现也不能向内灌水了，选取高度为3的围墙，比如：

发现可以灌水量为2，然后将此点灌水后的高度加入围墙，[1,4,3,1,3,2,3,4,2,3,3,2,3,1,3, 3]：

继续重复上边的步骤，知道堆为空

代码

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class TrappingRain2 {
    class Node{
        int val;
        int x;
        int y;
        Node(int val,int x,int y){
            this.val = val;
            this.x = x;
            this.y = y;
        }
    }
    public Comparator<Node> cmp = new Comparator<Node>(){
        public int compare(Node e1,Node e2){
            return e1.val-e2.val;
        }
    };

    public int trapRainWater(int[][] heightMap) {
        if(heightMap.length == 0 || heightMap[0].length == 0){
            return 0;
        }
        boolean[][] visited = new boolean[heightMap.length][heightMap[0].length];
        Queue<Node> heap = new PriorityQueue<Node>(cmp);
        int sum = 0;
        int[] x_delta = {0,0,1,-1};
        int[] y_delta = {-1,1,0,0};
        //初始边界入堆
        for(int i = 0; i < heightMap.length;i++){
            for(int j = 0;j < heightMap[0].length;j++){
                if(i == 0 || j == 0 || i == heightMap.length-1 || j == heightMap[0].length-1){
                    heap.add(new Node(heightMap[i][j],i,j));
                    visited[i][j] = true;
                }
            }
        }

        while(!heap.isEmpty()){
            Node top =  heap.peek();
            heap.remove();
            for(int i = 0;i < 4;i++){
                int x_new = top.x+x_delta[i];
                int y_new = top.y+y_delta[i];
                if(x_new >=0 && x_new < heightMap.length && y_new >= 0 && y_new < heightMap[0].length && !visited[x_new][y_new]){
                    if(heightMap[x_new][y_new] < top.val){
                        sum += top.val-heightMap[x_new][y_new];
                        heap.add(new Node(top.val,x_new,y_new));
                    }
                    else{
                        heap.add(new Node(heightMap[x_new][y_new],x_new,y_new));
                    }
                    visited[x_new][y_new] = true;
                }
            }
        }
        return  sum;
    }

    public static void main(String[] args){
        TrappingRain2 test = new TrappingRain2();
        int[][] heightMap = {{1,4,3,1,3,2},{3,2,1,3,2,4},{2,3,3,2,3,1}};
        int sum = test.trapRainWater(heightMap);
        System.out.println(sum);
    }
}

Top K Frequent Words

题目

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

> Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
> Output: ["i", "love"]
> Explanation: "i" and "love" are the two most frequent words.
>     Note that "i" comes before "love" due to a lower alphabetical order.
>
>

>

Example 2:

> Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
> Output: ["the", "is", "sunny", "day"]
> Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
>     with the number of occurrence being 4, 3, 2 and 1 respectively.
>
>

>

Note:

1. You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
2. Input words contain only lowercase letters.

Follow up:

1. Try to solve it in O(n log k) time and O(n) extra space.

给定一个字符串数组，要求返回出现次数最多的前K个字符串，如果遇到多个字符串年出现次数相同时，则优先取字典序小的字符串。

分析

正常的能够想到的思路是用一个hashmap记录每个单词出现的次数，然后放入一个堆中，堆的排序依据是出现次数多的排在前面，出现次数一样多的，字典序小的排在前面，将全部字符放入堆之后弹出前K个，就得到了出现次数最多的前K个，复杂度:$O(nlogn)$

follow up : 要求我们用时$O(nlogn)$ ，也就是说我们只需要维护大小为K的堆，因此，我们应该采用“最小堆”而非“最大堆”，堆顶元素是当前出现次数最小的，所以当下一次有新元素加进来的时候，如果堆的大小超过了k，就可以把堆顶这个出现次数最少的元素弹掉了，这样一来，最后堆中剩下的k个元素都是出现次数最多得了，是不是很神奇~！！！！

所以这道题我们的堆应该是这样的：

1. 出现次数少的优先出堆
2. 出现次数一样的，字典序大的优先出队
3. 堆的大小为k,当堆中元素个数超过k时，手动poll出堆

这样一来，堆的大小就一直都只有K，时间复杂度就降到$O(klogn)$ 了。这在数据量很大的情况下是十分有必要的！！比如我们要在100亿个数字中找到最大的K个，如果用之前的建堆方法就要建一个100亿大的堆。。。超恐怖，但现在，无论多少数据，我们的堆也只有k那么大了

ps: 这里还学到了一个**比较器的神奇写法**，见注释，可以在比较器中调用map中的count来进行比较诶，这样heap里面就可以只存String了。

#### 代码

```java
import java.util.*;

public class TopKFrequentWords {
    class Node{
        String word;
        int count;
        Node(String word,int count){
            this.count = count;
            this.word = word;
        }
    }
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> map = new HashMap<>();
        Comparator<Node> cmp = new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if(o1.count!= o2.count) return o1.count-o2.count;//出现次数少的排在前面
                else {
                    if(o1.word.compareTo(o2.word) < 0){//在字母表中位置靠后的排在前面
                        return 1;
                    }
                    else return -1;
                }
            }
        };
//        Comparator<String> cmp2 = new Comparator<String>() {
//            @Override
//            public int compare(String o1, String o2) {
//                int o1Count = map.get(o1), o2Count = map.get(o2);
//                if(o1Count!= o2Count) return o1Count-o2Count;//出现次数少的排在前面
//                else {
//                    return o2.compareTo(o1);
//                }
//            }
//        };
        PriorityQueue<Node> heap = new PriorityQueue<>(cmp);
        for(String word : words){
            map.put(word,map.getOrDefault(word,0)+1);
        }
        for(String word:map.keySet()){
            heap.add(new Node(word,map.get(word)));
            //手动控制heap大小
            if(heap.size() > k){
                heap.poll();
            }
        }
        List<String> res = new ArrayList<>();
        while (!heap.isEmpty()){
            res.add(heap.poll().word);
        }
        Collections.reverse(res);
        return res;
    }
}
```



### [Find Median from Data Stream](https://leetcode.com/problems/find-median-from-data-stream/)

#### 题目

> Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
>
> Examples: 
>
> `[2,3,4]` , the median is `3`
>
> `[2,3]`, the median is `(2 + 3) / 2 = 2.5`
>
> Design a data structure that supports the following two operations:
>
> - void addNum(int num) - Add a integer number from the data stream to the data structure.
> - double findMedian() - Return the median of all elements so far.
>
> For example:
>
> ```
> addNum(1)
> addNum(2)
> findMedian() -> 1.5
> addNum(3) 
> findMedian() -> 2
> ```

数据以流的方式给出，实现加入数字和获取中位数的方法。

#### 分析

baseline:每次加入数字之后排序，然后计算中位数，时间复杂度：$$O(n^2logn)$$

**优化：**

中位数：将元素分成两堆，一堆比中位数小，一堆比中位数大

在中位数左右设置两个堆，每次进来一个元素，和中位数比较，如果大于中位数，放到右边的堆中（小顶堆），比中位数小放到左边堆中（大顶堆）。

入堆之后，需要比较左右两个堆的元素个数，当两边数字个之差超过2时，则需要将多的一遍的元素挪出一个去另一边，以保证两边元素个数之差<=1

另外，每次需更新中位数，当左右两堆元素个数相等时，中位数为两个堆顶元素均值；当左右两堆元素个数相差一时，中位数为多的那个堆的堆顶元素

时间复杂度：$$O(nlogn)$$ ,n个元素入堆，入堆操作$$O(logn)$$

#### 代码

```java
import java.util.Comparator;
import java.util.PriorityQueue;

public class MedianFinder {
    PriorityQueue<Integer> maxHeap;//左边最大对
    PriorityQueue<Integer> minHeap;//右边最小堆
    int leftSum;
    int rightSum;
    double median;

    /** initialize your data structure here. */
    public MedianFinder() {
        Comparator<Integer> maxCmp = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        };
        maxHeap = new PriorityQueue<>(maxCmp);
        minHeap = new PriorityQueue<>();
        leftSum = 0;
        rightSum = 0;
        median = 0;
    }

    public void addNum(int num) {
        //如果两个堆都是空的,默认先放到右边堆中
        if(minHeap.isEmpty() && maxHeap.isEmpty()){
            minHeap.add(num);
            rightSum++;
            median = num;
        }
        //加入的值大于中位数，放入右边的堆
        else if(num > median){
            minHeap.add(num);
            rightSum++;
            //如果右边比左边多两个了，需要挪出一个去左边
            if(rightSum-leftSum == 2){
                maxHeap.add(minHeap.poll());
                leftSum++;
                rightSum--;
            }//此时两边元素相等或者右边比左边多一个
            if(rightSum > leftSum){
                median = minHeap.peek();
            }
            else {
                median = (minHeap.peek() + maxHeap.peek())/2.0;
            }
        }
        //否则，放入左边的堆
        else {
            maxHeap.add(num);
            leftSum++;
            //如果右边比左边多两个了，需要挪出一个去左边
            if(leftSum-rightSum == 2){
                minHeap.add(maxHeap.poll());
                leftSum--;
                rightSum++;
            }//此时两边元素相等或者右边比左边多一个
            if(leftSum > rightSum){
                median = maxHeap.peek();
            }
            else {
                median = (minHeap.peek() + maxHeap.peek())/2.0;
            }
        }
    }

    public double findMedian() {
        return median;
    }

}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
```



### [Sliding Window Median](https://leetcode.com/problems/sliding-window-median)   

上一题的follow up

#### 题目

> Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
>
> Examples: 
>
> `[2,3,4]` , the median is `3`
>
> `[2,3]`, the median is `(2 + 3) / 2 = 2.5`
>
> Given an array *nums*, there is a sliding window of size *k* which is moving from the very left of the array to the very right. You can only see the *k* numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.
>
> For example,
> Given *nums* = `[1,3,-1,-3,5,3,6,7]`, and *k* = 3.
>
> ```
> Window position                Median
> ---------------               -----
> [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
>
> ```
>
> Therefore, return the median sliding window as `[1,-1,-1,3,5,6]`.



#### 分析

阿西吧，做了一晚上==

跟上一题相比，这道题是个滑动窗口问题，滑窗问题可以拆解为：

1. 加一个元素
2. 删一个元素

所以跟上一题一样的思路，但每次需要删除窗口错过的那个元素，那么如何找到要删除的这个元素在左边还是右边呢？

1. 如果元素>median，则一定在右堆
2. 如果元素<median，则一定在左堆
3. 如果元素==median，则一定在两堆的堆顶

先用PriorityQueue写了一版，90ms

PriorityQueue中remove操作的时间复杂度是$$O(n)$$ ,鼓起勇气手码了个hashheap优化下，hashheap中remove操作时间复杂度是$$O(logn)$$ ,写了一晚上，186ms，想哭。。。。

看了比较快的解法，用TreeSet，之后弄懂了再来写

代码

PriorityQueue:

public class Solution {
        PriorityQueue<Integer> maxHeap;//左边最大对
        PriorityQueue<Integer> minHeap;//右边最小堆
        int leftSum;
        int rightSum;
        double median;

        /** initialize your data structure here. */
    public Solution(){
            Comparator<Integer> maxCmp = new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return Integer.compare(o2,o1);
                }
            };
            maxHeap = new PriorityQueue<>(maxCmp);
            minHeap = new PriorityQueue<>();
            leftSum = 0;
            rightSum = 0;
            median = 0;
        }

        public void addNum(int num) {
            //如果两个堆都是空的,默认先放到右边堆中
            if(minHeap.isEmpty() && maxHeap.isEmpty()){
                minHeap.add(num);
                rightSum++;
                median = num;
            }
            //加入的值大于中位数，放入右边的堆
            else if(num > median){
                minHeap.add(num);
                rightSum++;
                //如果右边比左边多两个了，需要挪出一个去左边
                if(rightSum-leftSum == 2){
                    maxHeap.add(minHeap.poll());
                    leftSum++;
                    rightSum--;
                }//此时两边元素相等或者右边比左边多一个
                if(rightSum > leftSum){
                    median = minHeap.peek();
                }
                else {
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
            }
            //否则，放入左边的堆
            else {
                maxHeap.add(num);
                leftSum++;
                //如果右边比左边多两个了，需要挪出一个去左边
                if(leftSum-rightSum == 2){
                    minHeap.add(maxHeap.poll());
                    leftSum--;
                    rightSum++;
                }//此时两边元素相等或者右边比左边多一个
                if(leftSum > rightSum){
                    median = maxHeap.peek();
                }
                else {
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
            }
        }
        public void remove(int num) {
            //如果要删除的在右边
            if ((num == median && minHeap.peek() == num)|| num > median) {
                minHeap.remove(num);
                rightSum--;
                //删完两边元素相等
                if(rightSum == leftSum){
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
                //删完右边比左边少一个
                else if(rightSum+1 == leftSum){
                    median = maxHeap.peek();
                }
                //删完右边比左边少两个
                else {
                    minHeap.add(maxHeap.poll());
                    rightSum++;
                    leftSum--;
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
            }
            //如果要删除的在左边
            else {
                maxHeap.remove(num);
                leftSum--;
                if(rightSum == leftSum){
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
                //删完左边比右边少一个
                else if(leftSum+1 == rightSum){
                    median = minHeap.peek();
                }
                //删完左边比右边少两个
                else {
                    maxHeap.add(minHeap.poll());
                    rightSum--;
                    leftSum++;
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
            }
        }

        public double findMedian() {
            return median;
        }


    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] res = new double[nums.length-k+1];
        for(int i = 0; i < k;i++){
            addNum(nums[i]);
        }
        res[0] = findMedian();
        for(int i = k;i < nums.length;i++){
            addNum(nums[i]);
            remove(nums[i-k]);
            res[i-k+1] = findMedian();
        }
        return res;
    }
}

HashHeap：

class Solution {
    class HashHeap {
    HashMap<Integer,Node> map;//存储元素值和在堆中的索引
    ArrayList<Integer> heap;
    int heapSize;
    boolean isMaxHeap;

    class Node{
        int idx;//节点在堆中的位置
        int count;//该数值出现次数
        Node(int idx,int count){
            this.idx = idx;
            this.count = count;
        }
    }

    public boolean isEmpty(){
        if(heapSize == 0){
            return true;
        }
        else return false;
    }

    HashHeap(boolean isMaxHeap){
        this.map = new HashMap<>();
        this.heap = new ArrayList<>();
        this.isMaxHeap = isMaxHeap;
        this.heapSize = 0;
    }


    //由数组构建最大堆
    public void Build(int[] nums){
        int counter = 0;
        for(int i : nums){
            System.out.println(counter);
            add(i);
            counter ++;
        }
    }

    //交换堆中节点
    public void swap(int i,int j){
        //获取ij在堆中指向的元素值
        int vali = heap.get(i);
        int valj = heap.get(j);

        //获取两个值在map中的个数
        int counti = map.get(vali).count;
        int countj = map.get(valj).count;

        //修改hashmap，把两个值对应的位置互换，count不变
        map.put(vali,new Node(j,counti));
        map.put(valj,new Node(i,countj));

        //交换堆中的节点值
        heap.set(i,valj);
        heap.set(j,vali);
    }

    //向上交换
    public void ShiftUp(int idx){
        int parentIdx = (idx-1)/2;
        if(parentIdx > -1 && idx < heapSize){
            //如果是最大堆而且孩子>父亲 || 是最小堆而且孩子<父亲,需要向上shift
            if((isMaxHeap && heap.get(parentIdx) < heap.get(idx)) ||
                   !isMaxHeap && heap.get(parentIdx) > heap.get(idx) ){
                swap(idx,parentIdx);
                ShiftUp(parentIdx);
            }
        }
    }

    //向下交换
    public void ShiftDown(int idx){
        int leftChildIdx = 2 * idx+1;
        int rightChildIdx = 2 * idx+2;
        int largestIdx = idx;
        if(leftChildIdx < heapSize){
            //如果是最大堆而且父亲节点小于孩子
            if((isMaxHeap && heap.get(idx) < heap.get(leftChildIdx)) ||
                    (!isMaxHeap && heap.get(idx) > heap.get(leftChildIdx))){
                largestIdx = leftChildIdx;
            }
        }

        if(rightChildIdx < heapSize){
            if((isMaxHeap && heap.get(largestIdx) < heap.get(rightChildIdx)) ||
                    (!isMaxHeap && heap.get(largestIdx) > heap.get(rightChildIdx))){
                largestIdx = rightChildIdx;
            }
        }
        if(largestIdx != idx){
            swap(idx,largestIdx);
            ShiftDown(largestIdx);
        }
    }

    //插入元素，值为n
    public void add(int n){
        //如果堆中已经有该元素了,放在原来的位置，heap不用动，map计数+1
        if(map.containsKey(n)){
            map.put(n,new Node(map.get(n).idx,map.get(n).count+1));
        }
        //如果堆中没有该元素
        else {
            map.put(n,new Node(heapSize,1));
            heap.add(n);
            heapSize++;
            ShiftUp(heapSize-1);
        }
    }
    //删除节点
    public void remove(int n){
        int idx = map.get(n).idx;
        int count = map.get(n).count;
        //如果该值的节点只有一个
        if(count == 1){
            swap(idx,heapSize-1);
            map.remove(n);///在map中删除
            heap.remove(heap.size()-1);
            heapSize--;
            //不知道
            ShiftUp(idx);
            ShiftDown(idx);//交换之后需要向下维护
        }
        //如果该值的节点有多个，heap不用动，map里count-1
        else {
            map.put(n, new Node(idx, count - 1));
        }
    }

    //弹出节点
    public int poll(){
        int peakVal = heap.get(0);
        int idx = map.get(peakVal).idx;
        int count = map.get(peakVal).count;
        //如果堆中只有一个该节点,需要与最后一个交换后维护，
        if(count == 1){
            //与最后一个交换
            swap(0,heapSize-1);
            heap.remove(heap.size()-1);
            heapSize--;
            ShiftUp(0);
            ShiftDown(0);
            map.remove(peakVal);//在map中删除
        }
        //如果堆中有多个，heap不用变，map中对应count--；
        else {
            map.put(peakVal,new Node(idx,count-1));
        }
        return peakVal;
    }

    //获取堆顶元素
    public int peek(){
        return heap.get(0);
    }
    }
    
        HashHeap maxHeap;//左边最大对
        HashHeap minHeap;//右边最小堆
        int leftSum;
        int rightSum;
        double median;

        /** initialize your data structure here. */
    public Solution(){
            Comparator<Integer> maxCmp = new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return Integer.compare(o2,o1);
                }
            };
            maxHeap = new HashHeap(true);
            minHeap = new HashHeap(false);
            leftSum = 0;
            rightSum = 0;
            median = 0;
        }

public void addNum(int num) {
            //如果两个堆都是空的,默认先放到右边堆中
            if(minHeap.isEmpty() && maxHeap.isEmpty()){
                minHeap.add(num);
                rightSum++;
                median = num;
            }
            //加入的值大于中位数，放入右边的堆
            else if(num > median){
                minHeap.add(num);
                rightSum++;
                //如果右边比左边多两个了，需要挪出一个去左边
                if(rightSum-leftSum == 2){
                    maxHeap.add(minHeap.poll());
                    leftSum++;
                    rightSum--;
                }//此时两边元素相等或者右边比左边多一个
                if(rightSum > leftSum){
                    median = minHeap.peek();
                }
                else {
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
            }
            //否则，放入左边的堆
            else {
                maxHeap.add(num);
                leftSum++;
                //如果右边比左边多两个了，需要挪出一个去左边
                if(leftSum-rightSum == 2){
                    minHeap.add(maxHeap.poll());
                    leftSum--;
                    rightSum++;
                }//此时两边元素相等或者右边比左边多一个
                if(leftSum > rightSum){
                    median = maxHeap.peek();
                }
                else {
                   median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
            }
        }


        public void remove(int num) {
            //如果要删除的在左边
            if(maxHeap.map.containsKey(num)){
                maxHeap.remove(num);
                leftSum--;
                //删完相等
                if(leftSum == rightSum){
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
                else if(leftSum+1 == rightSum){
                    median = minHeap.peek();
                }
                //删完左边比右边少两个
                else {
                    maxHeap.add(minHeap.poll());
                    rightSum--;
                    leftSum++;
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
            }
            //要删除的在右边
            else{
                minHeap.remove(num);
                rightSum--;
                //删完两边元素相等
                if(rightSum == leftSum){
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
                //删完右边比左边少一个
                else if(rightSum+1 == leftSum){
                    
                    median = maxHeap.peek();
                }
                //删完右边比左边少2个，要从左边挪一个过来
                else {
                    minHeap.add(maxHeap.poll());
                    leftSum--;
                    rightSum++;
                    median = minHeap.peek()/2.0 + maxHeap.peek()/2.0;
                }
            }
        }

        public double findMedian() {
            return median;
        }


    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] res = new double[nums.length-k+1];
        for(int i = 0; i < k;i++){
            addNum(nums[i]);
        }
        res[0] = findMedian();
        for(int i = k;i < nums.length;i++){
            addNum(nums[i]);
            remove(nums[i-k]);
            res[i-k+1] = findMedian();
            System.out.print(i);
        }
        return res;
    }
}

Deque双端队列

可以从两端进行插入和删除

Sliding Window Maximum

题目

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

> Window position                Max
> ---------------               -----
> [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
>
>

>

Therefore, return the max sliding window as [3,3,5,5,6,7].

给定数组和窗口大小，要求返回窗口滑动过程中每一个位置的最大值。

分析

方法一：

两层循环，找窗口k内的最大值，时间复杂度$O(n*k)$

方法二：

维护一个heap，窗口向前滑动时，加一个元素，减一个元素，堆顶元素即为窗口内最大元素，时间复杂度：$O(nlogk)$

方法三：双端队列Deque

我们用双向队列可以在O(N)时间内解决这题。当我们遇到新的数时，将新的数和双向队列的末尾比较，如果末尾比新数小，则把末尾扔掉，直到该队列的末尾比新数大或者队列为空的时候才住手。这样，我们可以保证队列里的元素是从头到尾降序的，由于队列里只有窗口内的数，所以他们其实就是窗口内第一大，第二大，第三大…的数。保持队列里只有窗口内数的方法和上个解法一样，也是每来一个新的把窗口最左边的扔掉，然后把新的加进去。然而由于我们在加新数的时候，已经把很多没用的数给扔了，这样队列头部的数并不一定是窗口最左边的数。这里的技巧是，我们队列中存的是那个数在原数组中的下标，这样我们既可以直到这个数的值，也可以知道该数是不是窗口最左边的数。这里为什么时间复杂度是O(N)呢？因为每个数只可能被操作最多两次，一次是加入队列的时候，一次是因为有别的更大数在后面，所以被扔掉，或者因为出了窗口而被扔掉。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int[] res = new int[nums.length-k+1];
        
        if(nums.length == 0 || k == 0){
            return new int[0];
        }
        //窗口尾后移
        for(int i = 0;i < nums.length;i++){
            //窗口第一个元素超过窗口，弹出
            if(!deque.isEmpty() && deque.peekFirst() < i-k+1){
                deque.poll();
            }
            //如果目前元素大于deque中队尾元素，将队尾元素弹出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
                deque.pollLast();
            }
            //加入idx
            deque.addLast(i);
            //每次窗口滑动之后将最大元素加入结果集合
            if(i >= k-1){
                res[i-k+1] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}