Sliding Window Maximum (Tối đa cửa sổ trượt) trong C++

Cho mảng nums và kích thước cửa sổ k. Cửa sổ trượt từ trái sang phải, mỗi bước dịch 1. Tìm giá trị lớn nhất trong mỗi cửa sổ.

Ví dụ

nums = [1,3,-1,-3,5,3,6,8], k = 3

Kết quả: [3, 3, 5, 5, 6, 8]

Thuật toán: Deque đơn điệu (Monotonic Deque)

Duy trì deque chứa chỉ số các phần tử, giá trị giảm dần từ đầu đến cuối.

• Đầu deque luôn là max của cửa sổ hiện tại.
• Khi thêm phần tử mới i:
  • Pop back khi nums[back] < nums[i] (loại bỏ phần tử nhỏ hơn, không bao giờ thành max).
  • Push i vào back.
• Khi trượt cửa sổ: pop front nếu front < i - k + 1 (ngoài cửa sổ).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> dq;
        if (nums.empty()) return ans;
        for (int i = 0; i < k; i++) {
            while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
        }
        for (int i = k; i < nums.size(); i++) {
            ans.push_back(nums[dq.front()]);
            while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
            while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
        }
        ans.push_back(nums[dq.front()]);
        return ans;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 3, -1, -3, 5, 3, 6, 8};
    print_vector(ob.maxSlidingWindow(v, 3));
    return 0;
}

Độ phức tạp

• Thời gian: O(n) — mỗi phần tử push/pop tối đa 1 lần.
• Không gian: O(k) — deque chứa tối đa k chỉ số.

Input / Output

Input:  {1,3,-1,-3,5,3,6,8}, k=3
Output: [3, 3, 5, 5, 6, 8]