sliding-window-maximum.js

/**
 * 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.
 *
 * 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?
 */

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
const maxSlidingWindow = (nums, k) => {
  const window = [];
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    if (window.length > 0 && window[0] === i - k) {
      window.shift();
    }

    while (window.length > 0 && nums[window[window.length - 1]] < nums[i]) {
      window.pop();
    }

    window.push(i);

    if (i >= k - 1) {
      result.push(nums[window[0]]);
    }
  }

  return result;
};

export { maxSlidingWindow };