Cửa Sổ Trượt Cực Đại
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Đề bài
Cho dãy $N$ số nguyên và một số $K$. Hãy tìm giá trị lớn nhất trong mỗi cửa sổ trượt kích thước $K$ liên tiếp.
Sử dụng deque để giải bài toán hiệu quả.
Dữ liệu vào
- Dòng đầu: hai số nguyên $N, K$ $(1 \le K \le N \le 10^6)$.
- Dòng thứ hai: $N$ số nguyên $a_1, a_2, \ldots, a_N$ $(|a_i| \le 10^9)$.
Dữ liệu ra
- In ra $N - K + 1$ số nguyên, cách nhau bởi dấu cách — giá trị lớn nhất của mỗi cửa sổ.
Ví dụ
| Input | Output |
|---|---|
| 8 3\n1 3 -1 -3 5 3 6 7 | 3 3 5 5 6 7 |
| 5 2\n1 2 3 4 5 | 2 3 4 5 |
Giới hạn
- $1 \le K \le N \le 10^6$
- $|a_i| \le 10^9$
- Thời gian: 1 giây
- Bộ nhớ: 256 MB
Community Discussion