JavaScript日拱演演算法題解滑動視窗的最大值範例

2022-10-18 14:01:27

題目：

給定一個陣列 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 陣列，然後執行刪除佇列頭元素、在佇列尾新增下一元素的操作；

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 迴圈裡面要對陣列一整個 Math.max，時間複雜度肯定爆表了，O(n*n)，不超時才怪。

第二反應

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

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

步驟拆解：

1、每當讀入的數大於隊尾，則迴圈刪除隊尾小於讀入元素的數位，保證佇列的遞減單調性

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

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

4、迴圈以上步驟，直到視窗的右邊界到隊尾

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.迴圈求解序列中的最大值
            //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;
};

小結：

除了以上兩種解法，還有其它思路，不得不說這題還是很有學問的。在處理滑動視窗問題中，經常會遇到要構造一個單調佇列，得著重記筆記記筆記。(ಥ﹏ಥ)

以上就是JavaScript日拱演演算法題解滑動視窗的最大值範例的詳細內容，更多關於JavaScript 滑動視窗最大值的資料請關注it145.com其它相關文章！

JavaScript日拱演演算法題解滑動視窗的最大值範例

目錄

題目：

題解：

第一反應

JavaScript 實現

第二反應

JS 實現

小結：

熱門文章