Problem #18 Sliding Window

All problems are from https://www.dailycodingproblem.com/

 

My Solution Codes : https://github.com/Kusin/DailyCoding

Kusin/DailyCoding

Daily Coding Problem#18: Sliding Window

Problem Description

 

Idea

This problem is finding a maximum vale of all rnage of a fixed length.

 

This problem can be solved by a technique called Sliding Window.

It uses data structure called deque, which we used for Problem #17.

 

1. prepare a deque. We will store elements in this deque monotone. (decreasing order)

2. enumerate elements from the beginning. pop elements from the end of deque to maintain deque monotone.

3. eliminate elements out or window. 

 

at each window, print the first element of deque. That will be the maximum value.

 

 

Problems using Sliding window.

https://code.sasa.hs.kr/problem.php?id=2295 

https://www.acmicpc.net/problem/11003

https://www.acmicpc.net/problem/8201

Implementation

from collections import deque
array =[int(i) for i in input().strip().split()]
k = int(input())
dq = deque()
ans=[]
for index,element in enumerate(array):
    while dq and dq[-1] < element:
        dq.pop()
    dq.append(element)
    if index>=k and dq[0] == array[index-k]:
        dq.popleft()
    if index >= k-1: # when window's size reached k
        ans.append(dq[0])
print(*ans)