Sliding Window Maximum
Python
Hard
3 views
Problem Description
Read n integers and window size k. For each window output maximum. Use deque logic.
Input Format
First line n k. Second line n integers.
Output Format
One line of maxima.
Sample Test Case
Input:
8 3
1 3 -1 -3 5 3 6 7
Official Solution
import sys
from collections import deque
p=sys.stdin.read().strip().split()
if len(p)<2: sys.exit(0)
n=int(p[0]); k=int(p[1])
a=list(map(int,p[2:2+n]))
dq=deque()
out=[]
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:
out.append(str(a[dq[0]]))
sys.stdout.write(' '.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!