239. Sliding Window Maximum

原题：239. Sliding Window Maximum

解法一

思路：滑动窗口，维护一个size为k的大堆。滑动过程中把最老的元素poll，offer最新的元素后调整堆。

时间复杂度：O(n * logk)

解法二（Recommend）

由于窗口大小固定，我们并不需要去维持大堆，只要记录窗口内的最大值即可。这里采用 双关队列（Dequeue） 的思路。

时间复杂度：O(n)

source code

// Runtime: 192 ms, faster than 18.08% of JavaScript online submissions for Sliding Window Maximum.
// Memory Usage: 48 MB, less than 33.33% of JavaScript online submissions for Sliding Window Maximum.

var maxSlidingWindow = function(nums, k) {
    const window = [];//存储的是nums的索引，这是时间复杂度为O(n)的关键
    const result = [];
    for(let i = 0; i<nums.length; i++) {
        const num = nums[i];
        for(let j = 0; j<window.length && window[j]<=i-k; j++) {//把超出窗口容量的最老的索引出列
            window.shift();
        }
        while(true) {
            if(window.length && nums[window[window.length-1]]<=num) {//每个新增的元素后续只会被比较一次就出列了，所以内层循环的时间复杂度为O(1)
                window.pop();
            }else {
                break;
            }
        }
        window.push(i);
        
        if(i>=k-1) {
            result.push(nums[window[0]]);
        }
    }

    return result;
};

test cases

test("test1", ()=>{
    expect(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)).toEqual([3,3,5,5,6,7]);
})

test("test2", ()=>{
    expect(maxSlidingWindow([1,3,1,2,0,5], 3)).toEqual([3,3,2,5]);
})