Sliding Window Maximum

Description

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.

Follow up:
Could you solve it in linear time?

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

 

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

Solution(javascript)

// 这个做法不行，最坏的情况还是 O(nk)，也可以用 Heap(O(nlogk))
// const maxSlidingWindow = (nums = [], k) => {
//   if (!nums.length) {
//     return []
//   }
//   const result = []
//   let currentMaxIndex = 0
//   const setMaxIndex = (index) => {
//     currentMaxIndex = index
//     for (let i = index; i < index + k; i++) {
//       if (nums[i] >= nums[currentMaxIndex]) {
//         currentMaxIndex = i
//       }
//     }
//   }
//   setMaxIndex(0)
//   result.push(nums[currentMaxIndex])
//   for (let i = 1; i < nums.length - k + 1; i++) {
//     if (nums[i + k - 1] > nums[currentMaxIndex]) {
//       currentMaxIndex = i + k - 1
//     } else if (i - 1 === currentMaxIndex) {
//       setMaxIndex(i)
//     }
//     result.push(nums[currentMaxIndex])
//   }
//   return result
// }

// 单调队列 O(n)
const maxSlidingWindow = (nums = [], k) => {
  if (!nums.length) {
    return []
  }
  const result = []
  const queue = []
  for (let i = 0; i < k; i++) {
    while (nums[i] > nums[queue[queue.length - 1]]) {
      queue.pop()
    }
    queue.push(i)
  }
  result.push(nums[queue[0]])
  for (let i = 1; i < nums.length - k + 1; i++) {
    if (queue[0] < i) {
      queue.shift()
    }
    while (nums[i + k - 1] > nums[queue[queue.length - 1]]) {
      queue.pop()
    }
    queue.push(i + k - 1)
    result.push(nums[queue[0]])
  }
  return result
}