Monotone Queue Technique
스터디를 하다가 알게 된 테크닉인데 꽤 유용하다.
Sliding Window에서 min/max 값을 찾을 때 유리하며 DP 최적화에도 쓰인다.
Sliding Window의 범위 안에서 최대값을 찾아야 한다거나, 합계를 기억해야 할 때 Brute Force로 접근하게 되면 배열의 길이 N만큼 돌면서 윈도우 사이즈 K만큼 반복된 연산을 계속 해줘야 한다. 이 경우 시간 복잡도는 O(N^K)가 될 것이다.
Monotone Queue Technique은 연산 대상을 linear scan을 하면서 조건에 맞는 최적의 값을 deque를 통해 트래킹하는 방식이며, 시간복잡도를 O(N)으로 줄일 수 있다.
sliding window에서 최대값 찾기 예제
아래와 같이 윈도우 사이즈 안에서 최대값을 찾고 싶다고 하자.
[8 4 5] 7 6 1 -> 8
8 [4 5 7] 6 1 -> 7
8 4 [5 7 6] 1 -> 7
8 4 5 [7 6 1] -> 7
가장 먼저 8, 4, 5를 deque에 넣어준다. 이때, k 사이즈를 넘어가는 값이 이미 큐에 들어있다면 제거해주고, 가장 최근에 입력된 값이 이전 값보다 크다면 이전 값을 밀어내도록 해야한다. 원하는 값이 queue의 가장 앞에 오도록 설계 하는 것이 핵심이다.
8, 4, 5가 들어있는 상태에서 두번째 윈도우로 이동한다고 해보자. 8은 사이즈를 벗어나므로 삭제된다. 7이 새로 들어오게 되는데 이미 들어있는 4, 5가 모두 7보다 작다. 그렇다면 4와 5를 지워준다. 이 다음으로 무엇이 들어오던지 7이 밀려나기 전까지는 7이 가장 큰 값임을 보장할 수 있다. 실제로 설정한 예제에서는 배열의 끝에 닿을 때까지 7이 가장 큰 값으로 유지된다.
이 문제를 구현한 코드는 아래와 같다. 다만 배열의 값을 deque에 직접 넣게 되면 size를 벗어나는 값이 무엇인지 찾기 힘드므로 배열의 인덱스를 넣어준다. 필요시 비교문에서 값을 조회해서 비교하면 된다.
class Solution {
private void cleanQueue(int i, int k){ // first one of queue is always biggest
// remove index out of sliding window -> do once
if(!dq.isEmpty() && dq.getFirst()==i-k) dq.removeFirst();
// remove indexes smaller than now one - keep the biggest one -> do max k-1 time
while(!dq.isEmpty() && nums[i] > nums[dq.getLast()]) dq.removeLast();
}
private ArrayDeque<Integer> dq = new ArrayDeque<Integer>(); // store index, not value
private int[] nums;
public int[] maxSlidingWindow(int[] nums, int k) {
int N = nums.length;
if(N*k==0) return new int[0];
if(k==1) return nums;
this.nums = nums;
int maxIdx = 0;
int maxValue[] = new int[N-(k-1)];
// init deque
for(int i=0; i<k; i++){
cleanQueue(i, k);
dq.addLast(i);
if(nums[i] > nums[maxIdx]) maxIdx = i;
}
maxValue[0] = nums[maxIdx];
// fill out max array
for(int i=k; i<N; ++i){
cleanQueue(i, k);
dq.addLast(i);
maxValue[i-(k-1)] = nums[dq.getFirst()];
}
return maxValue;
}
}이렇듯 monotone queue technique에서는 아래의 규칙을 지켜주면 된다.
- sliding window size와 같은 특정 범위를 벗어나면 큐에서 제거해주는 것
- 가장 첫번째 값은 min/max로 유지되도록 할 것
풀어보면 좋은 문제 리스트
239 sliding window maximum [hard]
1425 constrained subsequence sum [hard]
862 shortest subarray with sum at least k [hard]
209 Minimum Size Subarray Sum [medium]
1438 longest continuous subarray with absolute diff less than or equal to limit [medium]
