Sản Phẩm Nổi Bật Khung Giờ Siêu Thị Go!

Mô tả

Anh Tư là quản lý siêu thị Go! mới khai trương ở quận Gò Vấp. Để theo dõi sức mua theo thời gian thực, hệ thống máy POS ghi lại mã sản phẩm (một số nguyên) theo từng phút liên tiếp thành một dãy dài. Anh Tư muốn đánh giá độ hot của từng mặt hàng trong mỗi khung giờ kéo dài đúng K phút.

Cụ thể, cho dãy mã sản phẩm $A$ gồm $n$ phần tử, bạn hãy trượt một cửa sổ kích thước $K$ từ đầu đến cuối dãy. Ở mỗi vị trí cửa sổ, hãy xác định sản phẩm xuất hiện nhiều lần nhất. Nếu có nhiều sản phẩm cùng tần suất cao nhất, hãy chọn mã sản phẩm có giá trị nhỏ nhất. Kết quả thu được sẽ là một dãy các mã sản phẩm nổi bật ứng với từng khung giờ.

Đầu vào

Hàm nhận hai tham số:

• A: danh sách số nguyên dương biểu diễn mã sản phẩm theo thời gian.
• K: số nguyên dương, độ dài mỗi khung giờ (cửa sổ trượt).

Đầu ra

Trả về một danh sách các số nguyên là mã sản phẩm nổi bật của từng cửa sổ, theo thứ tự cửa sổ dịch chuyển từ trái sang phải.

Ràng buộc

• $1 \le n \le 10^5$
• $1 \le K \le n$
• $1\le A[i]$

Ví dụ

Ví dụ 1:

• Đầu vào: A = [1, 2, 2, 3, 3, 3, 1, 1], K = 3
• Đầu ra: [2, 2, 3, 3, 3, 1]

Giải thích từng bước:

• Cửa sổ [1, 2, 2]: mã 2 xuất hiện 2 lần, mã 1 xuất hiện 1 lần. Chọn 2.
• Cửa sổ [2, 2, 3]: mã 2 xuất hiện 2 lần, mã 3 xuất hiện 1 lần. Chọn 2.
• Cửa sổ [2, 3, 3]: mã 3 xuất hiện 2 lần, mã 2 xuất hiện 1 lần. Chọn 3.
• Cửa sổ [3, 3, 3]: mã 3 xuất hiện 3 lần. Chọn 3.
• Cửa sổ [3, 3, 1]: mã 3 xuất hiện 2 lần, mã 1 xuất hiện 1 lần. Chọn 3.
• Cửa sổ [3, 1, 1]: mã 1 xuất hiện 2 lần, mã 3 xuất hiện 1 lần. Chọn 1.

Ví dụ 2:

• Đầu vào: A = [5, 5, 5, 5], K = 2
• Đầu ra: [5, 5, 5]

Cửa sổ nào cũng chỉ chứa mã 5, nên kết quả đều là 5.