The challenge
Return the maximum value in every consecutive window of exactly k elements.
Use 1 ≤ k ≤ n. Values may be negative. Indices are zero-based.
Example
[1, 3, −1, −3, 5, 3, 6, 7], k = 3 → [3, 3, 5, 5, 6, 7].
Use the walkthrough below to inspect the input and each state change.
See Window maximum, step by step
Expand, shrink, and inspect the window state.
8 elements · zero-based indicesk = 3
Current windowRecorded answerOutside window
- Left
- 0
- Right
- -1
- Length
- 0
Step 01 / 16
Start with an empty window
Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.
left = 0; right = −1Answer so far
[]
View exact input
Input: [1,3,-1,-3,5,3,6,7] · k = 3
Current window is empty.
Put it into code
Keep candidate indices with decreasing values. A newer value that is at least as large dominates older smaller candidates and expires later.
Indices are zero-based. C++ uses C++17 or later.
from collections import deque
def window_maxima(nums, k):
candidates = deque() # Indices; values decrease front to back.
answer = []
for right, value in enumerate(nums):
left = right - k + 1
while candidates and candidates[0] < left:
candidates.popleft()
while candidates and nums[candidates[-1]] <= value:
candidates.pop()
candidates.append(right)
if left >= 0:
answer.append(nums[candidates[0]])
return answer#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
vector<int> window_maxima(const vector<int>& nums, int k) {
deque<int> candidates;
vector<int> answer;
for (int r = 0; r < (int)nums.size(); ++r) {
int left = r - k + 1;
while (!candidates.empty() && candidates.front() < left)
candidates.pop_front();
while (!candidates.empty() && nums[candidates.back()] <= nums[r])
candidates.pop_back();
candidates.push_back(r);
if (left >= 0) answer.push_back(nums[candidates.front()]);
}
return answer;
}