Mô Tả Câu Hỏi

Hiện tại chúng ta có một dãy số gồm N phần tử (N ≤ 10^6), cùng với một cửa sổ trượt có kích thước k. Cửa sổ này sẽ trượt từ bên trái sang phải, mỗi lần trượt một đơn vị. Nhiệm vụ là tìm giá trị lớn nhất và nhỏ nhất trong cửa sổ sau mỗi lần trượt.

Ví dụ:

Dãy số là [1, 3, -1, -3, 5, 3, 6, 7], và k = 3.

Định Dạng Nhập Xuất

Định dạng Nhập:

- Dòng đầu tiên chứa hai số nguyên n và k. - Dòng thứ hai chứa n số nguyên (< INT_MAX).

Định dạng Xuất:

- Dòng đầu tiên là các giá trị nhỏ nhất sau mỗi lần trượt của cửa sổ. - Dòng thứ hai là các giá trị lớn nhất sau mỗi lần trượt của cửa sổ.

Ví Dụ Nhập Xuất

8 3
1 3 -1 -3 5 3 6 7

-1 -3 -3 -3 3 3
3 3 5 5 6 7

Giải Pháp

Giải pháp đầu tiên mà nhiều người nghĩ đến là duyệt qua từng đoạn có độ dài k và tìm giá trị lớn nhất và nhỏ nhất trong mỗi đoạn. Tuy nhiên, phương pháp này có độ phức tạp, sẽ không đáp ứng được yêu cầu khi n lên đến 10^6.

Queue Đơn Điệu:

Queue đơn điệu là một cấu trúc dữ liệu có khả năng duy trì tính chất tăng dần hoặc giảm dần của các phần tử, đồng thời chỉ giữ tối đa k phần tử.おかげ của cấu trúc này, ta có thể tìm được giá trị lớn nhất và nhỏ nhất trong cửa sổ trượt một cách hiệu quả.

Phương Pháp:

Chúng ta sẽ duy trì hai queue:

• Queue max_queue để tìm giá trị lớn nhất.
• Queue min_queue để tìm giá trị nhỏ nhất.

Với mỗi phần tử mới, ta thực hiện các bước sau:

• Kiểm tra nếu phần tử mới có chỉ số vượt quá khoảng cách k so với phần tử đầu tiên của queue, nếu có thì loại bỏ phần tử đầu tiên.
• Đối với queue max_queue: loại bỏ các phần tử từ cuốiqueue nếu chúng nhỏ hơn phần tử mới.
• Đối với queue min_queue: loại bỏ các phần tử từ cuốiqueue nếu chúng lớn hơn phần tử mới.
• Thêm phần tử mới vào queue.

Khi cửa sổ đã đủ kích thước k, ta sẽ lấy giá trị đầu tiên của mỗi queue để lưu kết quả.

Code Giải Quyết

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

struct Element {
    int index;
    int val;
    Element(int i, int v) : index(i), val(v) {}
};

int n, k;
int max_values[1000005];
int min_values[1000005];
deque<Element> max_queue, min_queue;

void maintainMaxQueue(int index, int value) {
    if (max_queue.empty()) {
        max_queue.push_back(Element(index, value));
        return;
    }
    
    // Xóa phần tử đầu tiên nếu nó nằm ngoài cửa sổ
    while (!max_queue.empty() && max_queue.front().index <= index - k) {
        max_queue.pop_front();
    }
    
    // Xóa các phần tử cuốiqueue nếu chúng nhỏ hơn value
    while (!max_queue.empty() && max_queue.back().val <= value) {
        max_queue.pop_back();
    }
    
    max_queue.push_back(Element(index, value));
}

void maintainMinQueue(int index, int value) {
    if (min_queue.empty()) {
        min_queue.push_back(Element(index, value));
        return;
    }
    
    // Xóa phần tử đầu tiên nếu nó nằm ngoài cửa sổ
    while (!min_queue.empty() && min_queue.front().index <= index - k) {
        min_queue.pop_front();
    }
    
    // Xóa các phần tử cuốiqueue nếu chúng lớn hơn value
    while (!min_queue.empty() && min_queue.back().val >= value) {
        min_queue.pop_back();
    }
    
    min_queue.push_back(Element(index, value));
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        int value;
        cin >> value;
        
        maintainMaxQueue(i, value);
        maintainMinQueue(i, value);
        
        if (i >= k) {
            max_values[i] = max_queue.front().val;
            min_values[i] = min_queue.front().val;
        }
    }
    
    // In ra các giá trị nhỏ nhất
    for (int i = k; i <= n; ++i) {
        cout << min_values[i] << " ";
    }
    cout << endl;
    
    // In ra các giá trị lớn nhất
    for (int i = k; i <= n; ++i) {
        cout << max_values[i] << " ";
    }
    
    return 0;
}