Sliding Window Maximum

Given an integer array `arr` and an integer `k`, find the maximum value in each sliding window of size `k`. The output is an array of these maximums. Solved in O(n) time using a monotonic deque.

Input Format

arr = array of integers, k = window size

Output Format

array of integers (maximum of each subarray)

Constraints

  • 1 <= arr.length <= 10^5; -10^9 <= arr[i] <= 10^9; 1 <= k <= arr.length

Examples

Example 1:

Input:

arr = [1,3,-1,-3,5,3,6,7]
k = 3

Output:

[3,3,5,5,6,7]

Example 2:

Input:

arr = [1,2,3,1,4,5,2,3,6]
k = 3

Output:

[3,3,4,5,5,5,6]
Loading...
Sliding Window Maximum - Sliding Window