Queue
Array
Sliding Window
Monotonic Queue
Heap (Priority Queue)
Description
You are given an array of integers 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 1:
Input: nums = [1,3,-1,-3,5,3,6,7], 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
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
Solutions
Solution 1
Python3 Java C++ Go Rust JavaScript C#
class Solution :
def maxSlidingWindow ( self , nums : List [ int ], k : int ) -> List [ int ]:
q = [( - v , i ) for i , v in enumerate ( nums [: k - 1 ])]
heapify ( q )
ans = []
for i in range ( k - 1 , len ( nums )):
heappush ( q , ( - nums [ i ], i ))
while q [ 0 ][ 1 ] <= i - k :
heappop ( q )
ans . append ( - q [ 0 ][ 0 ])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public int [] maxSlidingWindow ( int [] nums , int k ) {
PriorityQueue < int []> q
= new PriorityQueue <> (( a , b ) -> a [ 0 ] == b [ 0 ] ? a [ 1 ] - b [ 1 ] : b [ 0 ] - a [ 0 ] );
int n = nums . length ;
for ( int i = 0 ; i < k - 1 ; ++ i ) {
q . offer ( new int [] { nums [ i ] , i });
}
int [] ans = new int [ n - k + 1 ] ;
for ( int i = k - 1 , j = 0 ; i < n ; ++ i ) {
q . offer ( new int [] { nums [ i ] , i });
while ( q . peek () [ 1 ] <= i - k ) {
q . poll ();
}
ans [ j ++] = q . peek () [ 0 ] ;
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public :
vector < int > maxSlidingWindow ( vector < int >& nums , int k ) {
priority_queue < pair < int , int >> q ;
int n = nums . size ();
for ( int i = 0 ; i < k - 1 ; ++ i ) {
q . push ({ nums [ i ], - i });
}
vector < int > ans ;
for ( int i = k - 1 ; i < n ; ++ i ) {
q . push ({ nums [ i ], - i });
while ( - q . top (). second <= i - k ) {
q . pop ();
}
ans . emplace_back ( q . top (). first );
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 func maxSlidingWindow ( nums [] int , k int ) ( ans [] int ) {
q := hp {}
for i , v := range nums [: k - 1 ] {
heap . Push ( & q , pair { v , i })
}
for i := k - 1 ; i < len ( nums ); i ++ {
heap . Push ( & q , pair { nums [ i ], i })
for q [ 0 ]. i <= i - k {
heap . Pop ( & q )
}
ans = append ( ans , q [ 0 ]. v )
}
return
}
type pair struct { v , i int }
type hp [] pair
func ( h hp ) Len () int { return len ( h ) }
func ( h hp ) Less ( i , j int ) bool {
a , b := h [ i ], h [ j ]
return a . v > b . v || ( a . v == b . v && i < j )
}
func ( h hp ) Swap ( i , j int ) { h [ i ], h [ j ] = h [ j ], h [ i ] }
func ( h * hp ) Push ( v any ) { * h = append ( * h , v .( pair )) }
func ( h * hp ) Pop () any { a := * h ; v := a [ len ( a ) - 1 ]; * h = a [: len ( a ) - 1 ]; return v }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31 use std :: collections :: VecDeque ;
impl Solution {
#[allow(dead_code)]
pub fn max_sliding_window ( nums : Vec < i32 > , k : i32 ) -> Vec < i32 > {
// The deque contains the index of `nums`
let mut q : VecDeque < usize > = VecDeque :: new ();
let mut ans_vec : Vec < i32 > = Vec :: new ();
for i in 0 .. nums . len () {
// Check the first element of queue, if it's out of bound
if ! q . is_empty () && ( i as i32 ) - k + 1 > ( * q . front (). unwrap () as i32 ) {
// Pop it out
q . pop_front ();
}
// Pop back elements out until either the deque is empty
// Or the back element is greater than the current traversed element
while ! q . is_empty () && nums [ * q . back (). unwrap ()] <= nums [ i ] {
q . pop_back ();
}
// Push the current index in queue
q . push_back ( i );
// Check if the condition is satisfied
if i >= (( k - 1 ) as usize ) {
ans_vec . push ( nums [ * q . front (). unwrap ()]);
}
}
ans_vec
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 /**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function ( nums , k ) {
let ans = [];
let q = [];
for ( let i = 0 ; i < nums . length ; ++ i ) {
if ( q && i - k + 1 > q [ 0 ]) {
q . shift ();
}
while ( q && nums [ q [ q . length - 1 ]] <= nums [ i ]) {
q . pop ();
}
q . push ( i );
if ( i >= k - 1 ) {
ans . push ( nums [ q [ 0 ]]);
}
}
return ans ;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 using System.Collections.Generic ;
public class Solution {
public int [] MaxSlidingWindow ( int [] nums , int k ) {
if ( nums . Length == 0 ) return new int [ 0 ];
var result = new int [ nums . Length - k + 1 ];
var descOrderNums = new LinkedList < int > ();
for ( var i = 0 ; i < nums . Length ; ++ i )
{
if ( i >= k && nums [ i - k ] == descOrderNums . First . Value )
{
descOrderNums . RemoveFirst ();
}
while ( descOrderNums . Count > 0 && nums [ i ] > descOrderNums . Last . Value )
{
descOrderNums . RemoveLast ();
}
descOrderNums . AddLast ( nums [ i ]);
if ( i >= k - 1 )
{
result [ i - k + 1 ] = descOrderNums . First . Value ;
}
}
return result ;
}
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def maxSlidingWindow ( self , nums : List [ int ], k : int ) -> List [ int ]:
q = deque ()
ans = []
for i , v in enumerate ( nums ):
if q and i - k + 1 > q [ 0 ]:
q . popleft ()
while q and nums [ q [ - 1 ]] <= v :
q . pop ()
q . append ( i )
if i >= k - 1 :
ans . append ( nums [ q [ 0 ]])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public int [] maxSlidingWindow ( int [] nums , int k ) {
int n = nums . length ;
int [] ans = new int [ n - k + 1 ] ;
Deque < Integer > q = new ArrayDeque <> ();
for ( int i = 0 , j = 0 ; i < n ; ++ i ) {
if ( ! q . isEmpty () && i - k + 1 > q . peekFirst ()) {
q . pollFirst ();
}
while ( ! q . isEmpty () && nums [ q . peekLast () ] <= nums [ i ] ) {
q . pollLast ();
}
q . offer ( i );
if ( i >= k - 1 ) {
ans [ j ++] = nums [ q . peekFirst () ] ;
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution {
public :
vector < int > maxSlidingWindow ( vector < int >& nums , int k ) {
deque < int > q ;
vector < int > ans ;
for ( int i = 0 ; i < nums . size (); ++ i ) {
if ( ! q . empty () && i - k + 1 > q . front ()) {
q . pop_front ();
}
while ( ! q . empty () && nums [ q . back ()] <= nums [ i ]) {
q . pop_back ();
}
q . push_back ( i );
if ( i >= k - 1 ) {
ans . emplace_back ( nums [ q . front ()]);
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 func maxSlidingWindow ( nums [] int , k int ) ( ans [] int ) {
q := [] int {}
for i , v := range nums {
if len ( q ) > 0 && i - k + 1 > q [ 0 ] {
q = q [ 1 :]
}
for len ( q ) > 0 && nums [ q [ len ( q ) - 1 ]] <= v {
q = q [: len ( q ) - 1 ]
}
q = append ( q , i )
if i >= k - 1 {
ans = append ( ans , nums [ q [ 0 ]])
}
}
return ans
}