[백준] 8201 Pilots

N이 300만이여서 NlogN 이 될까 싶지만 시간제한이 넉넉하므로 FASTIO 까지 써주니 1.9초로 통과는 했고 O(N) 풀이도 배워보았다. O(NlogN) 풀이 이분탐색 + 모노톤 큐로 풀 수 있다. 길이 K가 가능하다면 J(J<K) 는 항상 가능하므로 이분탐색을 적용할 수 있는 문제이고, 정해진 길이 K에 대해서 모노톤 덱으로 O(N)에 검사를 해준다면 O(NlogN)이 나온다. 최대값, 최소값을 위해 덱을 두개를 써야하고 덱 자체도 상수가 있기 때문에 그렇게 빠른 O(NlogN)은 아니다. O(N) 풀이 투포인터 + 모노톤 큐로 O(N)에 처리가 가능하다. 구간 [L, R] 을 유지한다. R이 증가할때 [L, R] 에 최대값 - 최소값이 t보다 크다면 모노톤하게 유지하고 있는 현..........

원문링크 : [백준] 8201 Pilots