각 k 크기의 연속 하위 배열의 최대값을 찾는 C++ 프로그램

<시간/>

n개의 요소와 값 k가 있는 배열이 있다고 가정합니다. 크기가 k인 인접한 각 부분배열의 최대값을 찾아야 합니다.

따라서 입력이 arr =[3,4,6,2,8], k =3과 같으면 출력은 다음과 같습니다. 크기 3의 연속 하위 배열은 [3,4,6], [4,6, 2], [6,2,8]이므로 최대 요소는 6, 6, 8입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

k 크기의 데크 Qi를 정의합니다.
i를 초기화하려면:=0, i
Qi가 비어 있지 않고 arr[i]>=arr[Qi의 마지막 요소]인 동안 다음을 수행합니다.
- Qi에서 마지막 요소 삭제
Qi 끝에 i 삽입

i <크기가 arr인 경우 업데이트(i를 1만큼 증가), 다음을 수행합니다.

디스플레이 arr[Qi의 첫 번째 요소]
Qi가 비어 있지 않고 Qi의 첫 번째 요소 <=i - k 동안 수행:
- Qi에서 전면 요소 삭제
Qi가 비어 있지 않고 arr[i]>=arr[Qi의 마지막 요소]인 동안 다음을 수행합니다.
- Qi에서 마지막 요소 삭제
Qi 끝에 i 삽입

디스플레이 arr[Qi의 첫 번째 요소]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int main(){
   vector<int> arr = {3,4,6,2,8};
   int k = 3;
   deque<int> Qi(k);
   int i;
   for (i = 0; i < k; ++i){
      while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
         Qi.pop_back();

         Qi.push_back(i);
     }
     for ( ; i < arr.size(); ++i){
        cout << arr[Qi.front()] << " ";
        while ( (!Qi.empty()) && Qi.front() <= i - k)
            Qi.pop_front();
        while ( (!Qi.empty()) && arr[i] >= arr[Qi.back()])
            Qi.pop_back();
        Qi.push_back(i);
    }
    cout << arr[Qi.front()] << endl;
}

입력

{3,4,6,2,8}, 3

출력

6 6 8