LeetCode 之 JavaScript 解答第239題 —— 滑動窗口最大值（Sliding W

spacewander 發布于2019-08-23 16:59 / 1492人閱讀

摘要：你只可以看到在滑動窗口內的數字。滑動窗口每次只向右移動一位。返回滑動窗口最大值。算法思路暴力破解法用兩個指針，分別指向窗口的起始位置和終止位置，然后遍歷窗口中的數據，求出最大值向前移動兩個指針，然后操作，直到遍歷數據完成位置。

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.

給定一個數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口 k 內的數字。滑動窗口每次只向右移動一位。

返回滑動窗口最大值。

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:

▉ 問題分析

暴力破解法

1）看到這個題目最容易想到的就是暴力破解法，借助一個 for 循環，兩個變量，整體移動窗口，然后每移動一次就在大小為 k 的窗口求出最大值。

2）但是這樣的解決效率非常低，如果數據非常大時，共有 n1 個數據，窗口大小為 n2（n1 遠遠大于 n2），時間復雜度為 n2(n1 - n2) 。也就是 n1 * n2，最壞時間復雜度為 n^2。

優先級隊列

1）每次移動窗口求最大值，以及在動態數據中求最大值，我們想到的就是優先級隊列，而優先級隊列的實現是堆這種數據結構，這道題用堆解決效率更高。如果對堆不熟悉，趕緊給自己補補功課吧！底部有我寫的文章鏈接。

2）通過堆的優化，向堆中插入數據時間復雜度為 logn ，所以時間復雜度為 nlogn。

▉ 算法思路

暴力破解法：

1）用兩個指針，分別指向窗口的起始位置和終止位置，然后遍歷窗口中的數據，求出最大值；向前移動兩個指針，然后操作，直到遍歷數據完成位置。

優先級隊列：

1）需要維護大小為 k 的大頂堆，堆頂就是當前窗口最大的數據，當移動窗口時，如果插入的數據大于堆頂的數據，將其加入到結果集中。同時要刪除數據，如果刪除的數據為最大數據且插入的數據小于刪除的數據時，向大小為 k 的以 logn 的時間復雜度插入，返回堆頂元素。

▉ 暴力破解法

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

▉ 優先級隊列

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

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

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

    // 移動窗口
    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;
};  



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

    // 插入到數組尾部
    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);
    }
}

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

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

    // 最大數據移到最后刪除
    heap[1] = heap[count];

    // 長度減一
    count--;
    // 刪除數據
    heap.pop();

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

// 從上到下堆化
const heapify = (heap,count,i) =>{
    while(true){
        // 存儲堆子節點的最大值下標
        let maxPos = i;

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

        // 如果沒有發生替換，則說明該堆只有一個結點（父節點）或子節點都小于父節點
        if(maxPos === i) break;

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

▉ 性能分析

暴力破解法

時間復雜度：O（n^2）.

空間復雜度：O（1）.

優先級隊列

時間復雜度：nlogn.

空間復雜度：O(1).

▉ 擴展

堆：

1）堆插入、刪除操作

2）如何實現一個堆？

3）堆排序

4）堆的應用

詳細查看寫的另一篇關于堆的文章：數據結構與算法之美【堆】

歡迎一起加入到 LeetCode 開源 Github 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...
歡迎關注我個人公眾號：「一個不甘平凡的碼農」，記錄了自己一路自學編程的故事。

云服務器 GPU云服務器 javascript算法題 javascript滑動條 javascript圖片滑動 javascript左右滑動

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/103623.html

leetcode239. Sliding Window Maximum

摘要：題目要求假設有一個數組和一個長度為的窗口，數組長度。當窗口右滑時，會刪除下標上的值，并加入下標上的值。此時中記錄的值編程了，并返回當前的最大值為。一旦最大值失效，就從窗口中重新找一個最大值就好了。題目要求 Given an array nums, there is a sliding window of size k which is moving from the very lef...

sPeng 2019-08-15 14:22 評論0 收藏0
[Leetcode] Sliding Window Maximum 滑動窗口最大值

摘要：這樣，我們可以保證隊列里的元素是從頭到尾降序的，由于隊列里只有窗口內的數，所以他們其實就是窗口內第一大，第二大，第三大的數。 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...

lvzishen 2019-08-14 12:46 評論0 收藏0
[LeetCode] 239. Sliding Window Maximum

摘要：丟棄隊首那些超出窗口長度的元素隊首的元素都是比后來加入元素大的元素，所以存儲的對應的元素是從小到大 Problem 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...

lentoo 2019-08-16 13:45 評論0 收藏0
LeetCode 之 JavaScript 解答第104題 —— 二叉樹的最大深度

摘要：小鹿題目二叉樹的最大深度給定一個二叉樹，找出其最大深度。二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。求二叉樹的深度，必然要用到遞歸來解決。分別遞歸左右子樹。 Time：2019/4/22Title: Maximum Depth of Binary TreeDifficulty: MediumAuthor:小鹿題目：Maximum Depth of Binary Tre...

boredream 2019-08-23 17:07 評論0 收藏0
LeetCode 之 JavaScript 解答第98題 —— 驗證二叉搜索樹

摘要：小鹿題目驗證二叉搜索樹給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。假設一個二叉搜索樹具有如下特征節點的左子樹只包含小于當前節點的數。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來返回是否為二叉搜索樹。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

用戶84 2019-08-23 17:12 評論0 收藏0