Giả sử chúng ta có mảng n phần tử và giá trị k. Phải tìm giá trị lớn nhất cho mỗi mảng con liên tiếp kích thước k.
Ví dụ: arr = [3,4,6,2,8], k = 3. Các mảng con: [3,4,6], [4,6,2], [6,2,8]. Max lần lượt: 6, 6, 8.
Giải thuật
Sử dụng deque để duy trỉ các chỉ số phần tử có giá trị giảm dần:
- Khởi tạo deque Qi
- Xử lý k phần tử đầu: loại bỏ phần tử nhỏ hơn từ cuối, thêm chỉ số
- Duyệt từ k đến n-1:
- In arr[Qi.front()] (max cửa sổ hiện tại)
- Loại bỏ chỉ số ngoài cửa sổ từ đầu deque
- Loại bỏ phần tử nhỏ hơn arr[i] từ cuối deque
- Thêm i vào deque
- In phần tử cuối cùng: arr[Qi.front()]
Ví dụ minh họa
#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