구간에서의 최솟값 찾기, 슬라이딩 윈도우

임의의 배열과 일정한 간격이 주어졌을 때, 일정한 간격 안에서의 최솟값을 찾는 알고리즘을 슬라이딩 윈도우라고 한다

배열의 길이를 N이라고 할 때 각 구간에서의 최솟값을 O(N)의 시간복잡도에서 해결할 수 있다

 

자료구조는 deque, 덱을 이용한다. 덱의 맨 앞에 최솟값을 위치시키고 다음과 같은 과정으로 슬라이딩 윈도우 알고리즘은 진행된다

1. 앞의 원소가 구간 L에 들어있는지 인덱스 검사를 하고 범위 밖에 있는 원소라면 제거한다. 그리고 2번 과정으로 들어간다

2. 뒤에서부터 자신보다 작은 최솟값들은 제거한다. 왜냐하면 뒤의 구간에서 현재 값보다 작기 때문에 최솟값이 될 수 없다. 제거하면서 자신보다 작은 값을 만나면 뒤에 바로 원소를 넣는다

3. 1, 2 과정을 거치고 나서 맨 앞에 있는 값이 최솟값이기 때문에 그 값을 출력한다