6059 : 슬라이딩 윈도우 최소
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
크기 N인 배열에서 크기 K인 슬라이딩 윈도우가 이동할 때, 각 윈도우의 최솟값을 출력하시오.
$O(N)$ 단조 덱(Monotonic Deque)을 사용하여 구현하시오.
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 윈도우 크기 $K$: $1 \le K \le N$ (정수)
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
$O(N)$ 단조 덱(Monotonic Deque)을 사용하여 구현하시오.
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 윈도우 크기 $K$: $1 \le K \le N$ (정수)
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
입력 설명
첫째 줄에 N (1 ≤ N ≤ 100,000)과 K (1 ≤ K ≤ N).
둘째 줄에 N개의 정수.
둘째 줄에 N개의 정수.
출력 설명
각 윈도우의 최솟값을 공백으로 구분하여 출력합니다. (총 N-K+1개)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8 3
1 3 -1 -3 5 3 6 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
-1 -3 -3 -3 3 3도움
단조 증가 덱을 유지합니다: 새 원소가 들어올 때 덱 뒤에서 자신보다 크거나 같은 원소를 제거합니다.