https://leetcode.com/problems/sliding-window-maximum/

slidingWindowMaximum.js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    
    if(!nums.length || !k) return []; // because leetcode
    
    const result = [];
    
    // initialize window
    const window = [];
    for(let i=0; i<k; i++){
        window.push(i);
        removeRedundantValues(window, 0);
    }
    result.push(nums[window[0]]);
    
    for(let i=k; i<nums.length; i++){
        window.push(i);
        removeRedundantValues(window, i-k+1);
        result.push(nums[window[0]]);
    }
    
    return result;
    
    // private helper ensures that the value
    // at the left-most corner of the queue
    // is always the max for the current window
    function removeRedundantValues(window, startIndex){
        // remove indices below the startIndex (out of bounds)
        while(window[0] < startIndex) window.shift(); // O(n). In reality, should use Queue

        // destructively remove the right most element to the left,
        // popping off values that are less than or equal to itself
        let val = nums[window[window.length-1]];
        while(window.length >=2 && val > nums[window[window.length-2]]){
            const tmp = window.pop();
            window.pop();
            window.push(tmp);
        }
    }
};