24.06.13

2023. 06. 13 목요일

 

- 슬라이딩 윈도우로 각 구간의 최댓값을 구하는 방법?

: Deque를 사용한다. 구간의 너비를 k라고 할 때, 각 원소를 index와 값으로 묶는다.

(Deque에 index만 저장하여 값의 비교는 원소[index]의 방법도 있다)

 

다음과 같은 규칙으로 알고리즘을 작성한다.

1. Deque의 peekFirst의 index가 현재 구간의 index 범위보다 벗어난 경우 제거한다.

(ex. k = 3인 상황에서, index가 4일 때 Deque의 peekFirst에 1이 들어가 있을 땐 제거)

2. 새로 들어올 원소가 Deque의 peekLast보다 작은지 검사하며,

역순으로 작은 값을 모두 제거 (pollLast)한다.

3. 새로 들어온 원소를 offerLast한다.

4. 매 순간의 최댓값은 Deque의 peekFirst가 된다.