Sliding Window Maximum (Algorithms)
Programming Interview
Medium
5 views
Problem Description
For each testcase you get n, k and n numbers. Output max of each window of size k (space-separated).
Input Format
First integer t. For each: n k then n integers.
Output Format
t lines window maximums.
Sample Test Case
Input:
1
8 3
1 3 -1 -3 5 3 6 7
Constraints
Sum of n over all testcases
Official Solution
import sys
from collections import deque
p=sys.stdin.read().strip().split()
if not p:
sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
for _ in range(t):
n=int(next(it)); k=int(next(it))
a=[int(next(it)) for _ in range(n)]
dq=deque()
ans=[]
for i,v in enumerate(a):
while dq and dq[0]<=i-k:
dq.popleft()
while dq and a[dq[-1]]<=v:
dq.pop()
dq.append(i)
if i>=k-1:
ans.append(str(a[dq[0]]))
out.append(' '.join(ans))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!