Funcia
Lv.3arraydequesliding-window

Sliding Window Maximum

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given an integer array nums and a window size k, slide a window of length k from left to right one step at a time and return the maximum inside the window at each position (nums.length - k + 1 values).

Examples

numskresult
[1, 3, -1, -3, 5, 3, 6, 7]3[3, 3, 5, 5, 6, 7]
[4, 2]1[4, 2]
[9, 8, 7, 6]4[9]

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(nums: int[], k: int) → int[]

Constraints

  • 1≤1 \le k ≤\le nums.length ≤200,000\le 200{,}000
  • −109≤-10^9 \le nums[i] ≤109\le 10^9

Expected complexity

Time
O(N)
Space
O(K)

Examples

numskExpected
[1,3,-1,-3,5,3,6,7]3[3,3,5,5,6,7]
[4,2]1[4,2]
[9,8,7,6]4[9]

Hint

Hint

Keep a deque of indices whose values are decreasing: pop smaller-or-equal values from the back before pushing, pop the front when it leaves the window, and the front is the window maximum. Each index enters and leaves once, so O(N)O(N). Rescanning every window is O(NK)O(NK) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251372 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness409verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.