Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Sliding Window Maximum

LeetCode #239Hard
Monotonic deque · the front is always the window max

Given an array nums and a window size k, return the maximum of every contiguous window of size k as the window slides from left to right.

Asked atAmazonGoogleMeta
step 1 / 34
1
3
-1
-3
5
3
6
7
[0][1][2][3][4][5][6][7]
window maxima
Brute force · re-scan every window
▸
1given nums, k
2for i ← 0 to n − k:
3    scan nums[i..i+k−1] for its max
4    append max to answer
5return answer
state
  • n8
  • k3

line 1For every window of size k, report its maximum. The obvious approach: slide a window across and, for each position, scan all k elements to find the biggest.