Elearning CodePath – CTP Online Judge

Số lớn nhất trong cửa sổ trượt

SW001

🟢 Hard #Sliding Window #Deque #Priority Queue #Data Structure

### 📌 Thông tin chung

---
### 📝 Định nghĩa

Cho một dãy $N$ số nhà (số nguyên) $A_1, A_2, \dots, A_N$.
Tại mỗi thời điểm, người giao hàng xem xét một nhóm gồm đúng $K$ ngôi nhà liên tiếp. Nhóm này tạo thành một cửa sổ trượt có kích thước $K$.

---
### 📝 Yêu cầu

Với mỗi nhóm $K$ ngôi nhà liên tiếp (tức là mỗi cửa sổ trượt cỡ $K$), hãy tìm ra **số nhà lớn nhất** (giá trị lớn nhất) trong cửa sổ đó.
In ra tất cả các số nhà lớn nhất tìm được theo thứ tự các nhóm từ trái sang phải.
Tổng cộng có $N - K + 1$ cửa sổ trượt.

---
### 📥 Định dạng Đầu vào

* Dòng đầu tiên chứa hai số nguyên $N$ (số ngôi nhà) và $K$ (kích thước cửa sổ trượt).
* Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ (số nhà/giá trị).

Giới hạn:
(Phần giới hạn bị thiếu trong đề bài gốc, ta giả định giới hạn phổ biến cho bài toán này)
* Giả định $N \le 10^5$.
* $A_i$ là số nguyên (có thể âm, như trong ví dụ).

---
### 📤 Định dạng Đầu ra

In ra trên một dòng duy nhất $N - K + 1$ số nguyên, là các giá trị lớn nhất của từng cửa sổ trượt cỡ $K$, các số cách nhau bởi một khoảng trắng.

---
### ✨ Ví dụ

| SlidingMaxNum.inp | SlidingMaxNum.out |
| :---: | :---: |
| `8 3` <br> `1 3 -1 -3 5 3 6 7` | `3 3 5 5 6 7` |

**Giải thích Ví dụ:**
$N=8, K=3$. Dãy: $(1, 3, -1, -3, 5, 3, 6, 7)$.

| Cửa sổ trượt | Dãy con | Số lớn nhất |
| :---: | :---: | :---: |
| $A[1..3]$ | $(1, 3, -1)$ | $\mathbf{3}$ |
| $A[2..4]$ | $(3, -1, -3)$ | $\mathbf{3}$ |
| $A[3..5]$ | $(-1, -3, 5)$ | $\mathbf{5}$ |
| $A[4..6]$ | $(-3, 5, 3)$ | $\mathbf{5}$ |
| $A[5..7]$ | $(5, 3, 6)$ | $\mathbf{6}$ |
| $A[6..8]$ | $(3, 6, 7)$ | $\mathbf{7}$ |

Kết quả: $3 \ 3 \ 5 \ 5 \ 6 \ 7$.

---
### 🏷 Ràng buộc

| Subtask | Giới hạn $N$ |  Tỷ lệ điểm |
| :--- | :--- | :--- |
| $1$ | $N \le 1000$ |  $30\%$ |
| $2$ | $N \le 10^5$ |  $70\%$ |

---

✅ Đã AC: 2 / 19 submissions