Cửa sổ trượt tìm phần tử lớn nhất bằng Monotonic Deque O(N)

Mục tiêu kiến thức

• Triển khai hàng đợi hai đầu đơn điệu giảm (collections.deque) lưu trữ chỉ số.
• Đạt độ phức tạp thời gian tuyến tính tối ưu O(N) thay vì O(N · K) duyệt vét cạn.
• Loại bỏ các phần tử lỗi thời ngoài phạm vi cửa sổ và duy trì tính chất đơn điệu.

Mô tả bài toán

Cho mảng số nguyên nums và một số nguyên k đại diện cho kích thước cửa sổ trượt. Cửa sổ dịch chuyển từ đầu đến cuối mảng, mỗi lần sang phải 1 vị trí.

Viết hàm max_sliding_window(nums: list[int], k: int) -> list[int]:

• Kiểm tra tính hợp lệ:
• Nếu nums rỗng hoặc k ≤ 0 hoặc k > len(nums), raise ValueError("Kich thuoc cua so khong hop le").
• Trả về danh sách các giá trị lớn nhất trong mỗi cửa sổ trượt độ dài k.
• Thuật toán bắt buộc phải chạy trong thời gian O(N) bằng collections.deque.

Ràng buộc

• Thời gian chạy tối đa: 1000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng kiểu dữ liệu và miền giá trị được mô tả.