โปรแกรม C ++ เพื่อค้นหาสูงสุดของ subarray ที่ต่อเนื่องกันขนาด k แต่ละขนาด

สมมติว่าเรามีอาร์เรย์ที่มีองค์ประกอบ n ตัวและมีค่า k เราจะต้องหาค่าสูงสุดสำหรับแต่ละ subarray ที่ต่อเนื่องกันของขนาด k

ดังนั้น ถ้าอินพุตเหมือนกับ arr =[3,4,6,2,8], k =3 เอาต์พุตจะเป็น อาร์เรย์ย่อยที่อยู่ติดกันขนาด 3 คือ [3,4,6], [4,6, 2], [6,2,8] ดังนั้นองค์ประกอบสูงสุดคือ 6, 6 และ 8

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดหนึ่ง deque Qi ของขนาด k
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• ในขณะที่ Qi ไม่ว่างเปล่าและ arr[i]>=arr[องค์ประกอบสุดท้ายของ Qi] ให้ทำ:
  • ลบองค์ประกอบสุดท้ายออกจาก Qi
• แทรก i ที่ส่วนท้ายของ 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