문제
Slide a window of size k across the list one step at a time and report the maximum inside each window. A deque keeps this O(n).
Implement window_maximums(numbers, k).
Input
numbers: The list of integers. k: The window size.
Output
Return the maximum of each window, left to right.
제약 조건
1 ≤ k ≤ length ≤ 200,000
예시
예시 1
입력:
k = 3
numbers = [1, 3, -1, -3, 5, 3, 6, 7]
예상 출력:
expected = [3, 3, 5, 5, 6, 7]입력:
long long k = 3;
std::vector<long long> numbers = {1, 3, -1, -3, 5, 3, 6, 7};
예상 출력:
std::vector<long long> expected = {3, 3, 5, 5, 6, 7};입력:
long k = 3;
long[] numbers = new long[] {1, 3, -1, -3, 5, 3, 6, 7};
예상 출력:
long[] expected = new long[] {3, 3, 5, 5, 6, 7};설명
Windows [1,3,-1], [3,-1,-3], [-1,-3,5], … have maxima 3, 3, 5, 5, 6, 7.
예시 2
입력:
k = 1
numbers = [4, 2]
예상 출력:
expected = [4, 2]입력:
long long k = 1;
std::vector<long long> numbers = {4, 2};
예상 출력:
std::vector<long long> expected = {4, 2};입력:
long k = 1;
long[] numbers = new long[] {4, 2};
예상 출력:
long[] expected = new long[] {4, 2};설명
Windows of one element are the elements themselves: [4, 2].
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
최댓값은 창에서 빠져나갈 수 있으므로, 값과 인덱스를 함께 갱신하는 구조가 필요합니다.
힌트 2
값이 내림차순이 되도록 후보 인덱스를 유지하고, 현재 창 밖의 것은 제거하세요.
힌트 3
첫 완성 창과 크기 1인 창을 주의하세요. 모든 답은 완성된 창에 대응해야 합니다.
예상 복잡도
시간 O(n), 추가 공간 O(k)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.