Chương trình C ++ để tìm tối đa mỗi mảng con liền kề có kích thước k

Giả sử chúng ta có một mảng với n phần tử và một giá trị k. Chúng ta sẽ phải tìm giá trị lớn nhất cho mỗi mảng con liền kề có kích thước k.

Vì vậy, nếu đầu vào giống như arr =[3,4,6,2,8], k =3, thì đầu ra sẽ là Các mảng con liền kề có kích thước 3 là [3,4,6], [4,6, 2], [6,2,8], vì vậy các phần tử tối đa là 6, 6 và 8.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một deque Qi có kích thước k
• để khởi tạo i:=0, khi i
• trong khi Qi không trống và arr [i]> =arr [phần tử cuối cùng của Qi], hãy thực hiện:
  • xóa phần tử cuối cùng khỏi Qi
• chèn i vào cuối Qi

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

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

Đầu ra

6 6 8