한 회사에서는 매주 금요일마다 직원들의 야근 시간을 기록한다.
총 N주 동안의 기록이 있으며, Ai는 i번째 금요일의 야근 시간(분)을 의미한다.
인사팀은 특정 기간 동안 야근 패턴이 안정적이었는지 분석하려고 한다.
어떤 연속한 금요일 구간 [l, r]에 대해
(구간 내 최대 야근 시간) - (구간 내 최소 야근 시간) ≤ K
를 만족하면, 해당 구간을 안정 금요일 연속 구간(Friday Overtime Streak) 이라고 한다.
인사팀은 만들 수 있는 모든 안정 금요일 연속 구간 중 가장 긴 구간의 길이를 구하려고 한다.
첫째 줄에 금요일 기록 수 N과 기준값 K가 주어진다.
둘째 줄에 N개의 정수 A1, A2, ..., AN이 공백으로 구분되어 주어진다.
가장 긴 안정 금요일 연속 구간의 길이를 출력한다.
1 ≤ N ≤ 200,0000 ≤ K ≤ 10^90 ≤ Ai ≤ 10^9
8 20
120 130 125 135 200 210 205 195
10 10
80 85 82 88 120 125 130 90 92 95
4
3
앞의 네 주
120 130 125 135
에서는
최대값 = 135
최소값 = 120
차이 = 15
이므로 조건을 만족한다.
하지만 다음 값 200을 포함하면
최대값 = 200
최소값 = 120
차이 = 80
이 되어 조건을 만족하지 않는다.
뒤의 네 주
200 210 205 195
도
210 - 195 = 15
이므로 조건을 만족한다.
따라서 가장 긴 안정 금요일 연속 구간의 길이는 4이다.
구간
80 85 82
에서는
최대값 = 85
최소값 = 80
차이 = 5
이므로 조건을 만족한다.
길이가 4 이상인 모든 구간은 최대값과 최소값의 차이가 10을 초과하게 된다.
따라서 가장 긴 안정 금요일 연속 구간의 길이는 3이다.
연속 구간의 최대값과 최소값을 빠르게 관리해야 한다.
이를 위해 다음 두 개의 덱을 사용한다.
- 최대값 후보를 저장하는 단조 감소 덱
- 최소값 후보를 저장하는 단조 증가 덱
오른쪽 포인터를 한 칸씩 증가시키면서 현재 금요일 기록을 구간에 포함한다.
만약
현재 최대값 - 현재 최소값 > K
가 되면 왼쪽 포인터를 이동시켜 조건을 다시 만족시킨다.
각 원소는 최대 한 번 삽입되고 한 번 제거되므로 전체 연산 수는 선형이다.
따라서 시간 복잡도는
O(N)
이며,
덱에 인덱스를 저장하므로 공간 복잡도는
O(N)
이다.
import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
max_q = deque()
min_q = deque()
left = 0
answer = 0
for right in range(N):
while max_q and A[max_q[-1]] < A[right]:
max_q.pop()
max_q.append(right)
while min_q and A[min_q[-1]] > A[right]:
min_q.pop()
min_q.append(right)
while A[max_q[0]] - A[min_q[0]] > K:
if max_q[0] == left:
max_q.popleft()
if min_q[0] == left:
min_q.popleft()
left += 1
answer = max(answer, right - left + 1)
print(answer)