Time：2019/4/16
Title: Sliding Window Maximum
Difficulty: Difficulty
Author: 小鹿

題目：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. Return the max sliding window.

給定一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)荆残。你只可以看到在滑動(dòng)窗口 k 內(nèi)的數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。

返回滑動(dòng)窗口最大值。

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

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

Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.

Follow up:
Could you solve it in linear time?

Solve:

▉ 問(wèn)題分析

暴力破解法

1）看到這個(gè)題目最容易想到的就是暴力破解法锣吼，借助一個(gè) for 循環(huán)，兩個(gè)變量蓝厌，整體移動(dòng)窗口玄叠，然后每移動(dòng)一次就在大小為 k 的窗口求出最大值。

2）但是這樣的解決效率非常低拓提，如果數(shù)據(jù)非常大時(shí)读恃，共有 n1 個(gè)數(shù)據(jù)，窗口大小為 n2（n1 遠(yuǎn)遠(yuǎn)大于 n2），時(shí)間復(fù)雜度為 n2(n1 - n2) 狐粱。也就是 n1 * n2舀寓，最壞時(shí)間復(fù)雜度為 n^2。

優(yōu)先級(jí)隊(duì)列

1）每次移動(dòng)窗口求最大值肌蜻，以及在動(dòng)態(tài)數(shù)據(jù)中求最大值互墓，我們想到的就是優(yōu)先級(jí)隊(duì)列，而優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)是堆這種數(shù)據(jù)結(jié)構(gòu)蒋搜，這道題用堆解決效率更高篡撵。如果對(duì)堆不熟悉，趕緊給自己補(bǔ)補(bǔ)功課吧豆挽！底部有我寫(xiě)的文章鏈接育谬。

2）通過(guò)堆的優(yōu)化，向堆中插入數(shù)據(jù)時(shí)間復(fù)雜度為 logn 帮哈，所以時(shí)間復(fù)雜度為 nlogn膛檀。

▉ 算法思路

暴力破解法：

1）用兩個(gè)指針，分別指向窗口的起始位置和終止位置娘侍，然后遍歷窗口中的數(shù)據(jù)咖刃，求出最大值；向前移動(dòng)兩個(gè)指針憾筏，然后操作嚎杨，直到遍歷數(shù)據(jù)完成位置。

優(yōu)先級(jí)隊(duì)列：

1）需要維護(hù)大小為 k 的大頂堆氧腰，堆頂就是當(dāng)前窗口最大的數(shù)據(jù)枫浙，當(dāng)移動(dòng)窗口時(shí)，如果插入的數(shù)據(jù)大于堆頂?shù)臄?shù)據(jù)古拴，將其加入到結(jié)果集中箩帚。同時(shí)要?jiǎng)h除數(shù)據(jù)，如果刪除的數(shù)據(jù)為最大數(shù)據(jù)且插入的數(shù)據(jù)小于刪除的數(shù)據(jù)時(shí)斤富，向大小為 k 的以 logn 的時(shí)間復(fù)雜度插入膏潮，返回堆頂元素。

▉ 暴力破解法

var maxSlidingWindow = function(nums, k) {
    if(k > nums.length || k === 0) return [];
    let res = [], maxIndex = -1;
    for(let l = 0, r = k-1;r < nums.length;l++, r++){
        if(maxIndex < l){
            // 遍歷求出最大值
            let index = l;
            for(let i = l;i <= r;i++) {
                if(nums[i] > nums[index]) index = i;
            }
            maxIndex = index;
        }
        if(nums[r] > nums[maxIndex]){
            maxIndex = r;
        }
        res.push(nums[maxIndex]);
    }
    return res;
};

▉ 優(yōu)先級(jí)隊(duì)列

let count = 0;
let heap = [];
let n = 0;
var maxSlidingWindow = function(nums, k) {
    let pos = k;
    n = k;
    let result = [];
    let len = nums.length;

    // 判斷數(shù)組和最大窗口樹(shù)是否為空
    if(nums.length === 0 || k === 0) return result;

    // 建大頂堆
    let j = 0
    for(;j < k; j++){
        insert(nums[j]);
    }
    result.push(heap[1]); 

    // 移動(dòng)窗口
    while(len - pos > 0){
        if(nums[k] > heap[1]){
            result.push(nums[k]);
            insert(nums[k]);
            nums.shift();
            pos++; 
        }else{
            if(nums.shift() === heap[1]){
                removeMax(); 
            }
            insert(nums[k-1]);
            result.push(heap[1]);
            pos++;
        }
    }
    return result;
};  



// 插入數(shù)據(jù)
const insert = (data) =>{
    //判斷堆滿
    // if(count >= n) return; // >=

    // 插入到數(shù)組尾部
    count++
    heap[count] = data;

    //自下而上堆化
    let i = count;
    while(i / 2 > 0 && heap[i] > heap[parseInt(i/2)]){
        swap(heap,i,parseInt(i/2));
        i = parseInt(i/2);
    }
}

// 兩個(gè)數(shù)組內(nèi)元素交換
swap = (arr,x,y) =>{
    let temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

// 堆的刪除
const removeMax = () =>{
    // 判斷堆空
    if(count <= 0) return ;

    // 最大數(shù)據(jù)移到最后刪除
    heap[1] = heap[count];

    // 長(zhǎng)度減一
    count--;
    // 刪除數(shù)據(jù)
    heap.pop();

    // 從上到下堆化
    heapify(heap,count,1);
}

// 從上到下堆化
const heapify = (heap,count,i) =>{
    while(true){
        // 存儲(chǔ)堆子節(jié)點(diǎn)的最大值下標(biāo)
        let maxPos = i;

        // 左子節(jié)點(diǎn)比父節(jié)點(diǎn)大
        if(i*2 < n && heap[i*2] > heap[i]) maxPos = i*2;
        // 右子節(jié)點(diǎn)比父節(jié)點(diǎn)大
        if(i*2+1 <= n && heap[i*2+1] > heap[maxPos]) maxPos = i*2+1;

        // 如果沒(méi)有發(fā)生替換满力，則說(shuō)明該堆只有一個(gè)結(jié)點(diǎn)（父節(jié)點(diǎn)）或子節(jié)點(diǎn)都小于父節(jié)點(diǎn)
        if(maxPos === i) break;

        // 交換
        swap(heap,maxPos,i);
        // 繼續(xù)堆化
        i = maxPos;
    }
}

▉ 性能分析

暴力破解法

• 時(shí)間復(fù)雜度：O（n^2）.
• 空間復(fù)雜度：O（1）.

優(yōu)先級(jí)隊(duì)列

• 時(shí)間復(fù)雜度：nlogn.
• 空間復(fù)雜度：O(1).

▉ 擴(kuò)展

堆：

1）堆插入焕参、刪除操作

2）如何實(shí)現(xiàn)一個(gè)堆？

3）堆排序

4）堆的應(yīng)用

詳細(xì)查看寫(xiě)的另一篇關(guān)于堆的文章：數(shù)據(jù)結(jié)構(gòu)與算法之美【堆】