สมมติว่าเรามีอาเรย์ n สมาชิก และค่า k ต้องหาค่าสูงสุดของแต่ละซับอาเรย์ติดกันขนาด k
เช่น arr = [3,4,6,2,8], k = 3 ผลลัพธ์: 6 6 8
ซับอาเรย์ขนาด 3 คือ [3,4,6], [4,6,2], [6,2,8] ค่าสูงสุดคือ 6, 6, 8
ขั้นตอนการแก้ปัญหา (Sliding Window + Deque)
- สร้าง deque Qi
- ประมวลผล k ตัวแรก: ลบตัวเล็กกว่าหรือเท่ากับตัวปัจจุบันจากท้าย deque, เพิ่ม index ปัจจุบัน
- วนลูป i จาก k ถึง n-1:
- พิมพ์ arr[Qi.front()] (ค่าสูงสุดของหน้าต่างก่อนหน้า)
- ลบ index ที่อยู่นอกหน้าต่าง (≤ i-k) จากหน้า deque
- ลบตัวเล็กกว่าหรือเท่ากับตัวปัจจุบันจากท้าย deque
- เพิ่ม index ปัจจุบัน
- พิมพ์ arr[Qi.front()] สำหรับหน้าต่างสุดท้าย
ตัวอย่างโค้ด
#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
