JavaScript日拱算法題解滑動窗口的最大值示例

更新時間：2022年10月15日 10:05:11 作者：掘金安東尼

這篇文章主要為大家介紹了JavaScript日拱算法題解滑動窗口的最大值實現示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪

題目：

給定一個數組 nums 和滑動窗口的大小 k，請找出所有滑動窗口里的最大值。

示例:
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7] 
解釋: 
  滑動窗口的位置                最大值
---------------               -----
[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

題目來源：劍指 Offer 59 - I. 滑動窗口的最大值

題解：

第一反應

有時候搞不太懂力扣對于難度等級的判定，此題為“困難”？

用長度為 k 的數組去遍歷 nums 就可以了，每次拿到它的最大值，然后push進結果數組中，再返回不就行了？

分步解析：

1.找到窗口從頭滑到尾需要滑動的次數為： nums.length - k + 1；

2.初始化隊列；

3.每次滑動的時候，找到當前窗口的最大值保存到 res 數組，然后執(zhí)行刪除隊列頭元素、在隊列尾添加下一元素的操作；

JavaScript 實現

var maxSlidingWindow = function(nums, k) {
    if (nums.length == 0 || k > nums.length) return []
    var index = k
    var len = nums.length - k + 1
    var stack = [], res = []
    for (var j = 0; j < k; j++) {
        stack.push(nums[j])
    }
    for (i = 0; i < len; i++) {
        if (i !== 0) {
            stack.shift()
            stack.push(nums[index])
            index++
        }
        res.push(Math.max.apply(null, stack))
    }
    return res
};

提交看看，結果報錯“超出時間限制” QAQ

噢噢，再回看算法，for 循環(huán)里面要對數組一整個 Math.max，時間復雜度肯定爆表了，O(n*n)，不超時才怪。

第二反應

正解：轉換思路 采用單調數列

依次將數組的下標push到窗口中，超出窗口的shift掉，窗口是個單調遞減隊列，隊頭元素就是當前窗口的最大值；

步驟拆解：

1、每當讀入的數大于隊尾，則循環(huán)刪除隊尾小于讀入元素的數字，保證隊列的遞減單調性

2、如果單調的隊首（極大值），等于窗口左邊界的上一位，則說明極大值已經超出窗口，移除單調遞減隊列的隊首

3、每次窗口滑動的最大值為，單調遞減隊列的隊首

4、循環(huán)以上步驟，直到窗口的右邊界到隊尾

JS 實現

var maxSlidingWindow = function(nums, k) {
     const res = []; //保存滑動窗口的最大值
    const q = []; //滑動窗口隊列
    for (let i = 0; i < nums.length; i++) {
        //1.在隊尾添加元素num[i]
        var last = q.length - 1; //隊列的最后一個元素的索引
        while (last >= 0 && nums[i] > q[last]) { //2.循環(huán)求解序列中的最大值
            //2.求隊列中的最大值：如果新入隊列的元素，比隊尾元素大，隊尾被更新成新入隊列的元素,保證隊頭為隊列中的最大元素
            q.pop(); //隊尾移除，
            last = q.length - 1; //隊列更新長度
        }
        q.push(nums[i]); //入隊列
        // 當窗口i + 1 - k >= 0時，窗口滿了有三個數了
        const j = i + 1 - k;     //窗口向右滑動過程中最后一個元素的索引。
        if (j >= 0) {
            res.push(q[0]); //保存每一次k個窗口的最大值
            if (nums[j] === q[0]) { //3.向有滑動過程中，如果序列中的最大元素即退出窗口，則移除隊列頭部元素
                q.shift(); // 
            }
        }
    }
    return res;
};