noodleProblems/
Sliding Window Maximum
#119

Sliding Window Maximum

AlgorithmhardArrayQueueSliding WindowMonotonic StackHeap Priority Queue

Given an integer array nums and a window size k, a window of k consecutive elements slides from the left end of the array to the right, one position at a time.

Return an array of the **maximum** value in each window position, in order from left to right.

Example cases

  • classic
    in nums = [1,3,-1,-3,5,3,6,7], k = 3
    out [3,3,5,5,6,7]
    The max of each of the six windows of width 3, slid left to right.
  • single window size
    in nums = [9,11], k = 2
    out [11]
  • k = 1
    in nums = [4,2,12,11], k = 1
    out [4,2,12,11]
    Each element is its own window.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= k <= nums.length
  • -10^4 <= nums[i] <= 10^4
Saved
nums =
[1,3,-1,-3,5,3,6,7]
k =
3