Elearning CodePath – CTP Online Judge

PHẦN TỬ LỚN HƠN GẦN NHẤT BÊN TRÁI

ST_LeftBigger

🟢 Easy #Stack

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho một dãy số gồm $N$ số nguyên dương $a_1, a_2, \dots, a_n$. Với mỗi vị trí $i$ ($1 \le i \le N$), hãy tìm vị trí $j$ gần nhất về phía bên trái ($j < i$) thỏa mãn điều kiện $a_j > a_i$.

Yêu cầu: In ra vị trí $j$ tìm được cho mỗi vị trí $i$. Nếu không có phần tử nào thỏa mãn, in ra -1.

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

Dữ liệu vào từ file văn bản ST_LeftBigger.INP gồm:
- Dòng đầu tiên chứa số nguyên dương $N$ là số lượng phần tử trong danh sách ($1 \le N \le 10^6$).
- Dòng tiếp theo chứa $N$ số nguyên $a_1, a_2, \dots, a_n$ cách nhau bởi dấu cách ($0 \le a_i \le 10^9$).

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

Ghi ra file văn bản ST_LeftBigger.OUT:
- $N$ số nguyên tương ứng là các vị trí $j$ tìm được, các số cách nhau bởi một dấu cách.

### ✨ Ví dụ

| ST_LeftBigger.INP | ST_LeftBigger.OUT |
| :--- | :--- |
| 7 <br> 2 1 3 2 8 5 7 | -1 1 -1 3 -1 5 5 |

**Giải thích:**
- $i=1 (a_1=2)$: Không có phần tử bên trái $\Rightarrow -1$.
- $i=2 (a_2=1)$: Bên trái có $a_1=2 > 1$, vị trí gần nhất là $1$.
- $i=3 (a_3=3)$: Bên trái không có số nào lớn hơn 3 $\Rightarrow -1$.
- $i=4 (a_4=2)$: Bên trái có $a_3=3 > 2$, vị trí gần nhất là $3$.
- $i=5 (a_5=8)$: Bên trái không có số nào lớn hơn 8 $\Rightarrow -1$.
- $i=6 (a_6=5)$: Bên trái có $a_5=8 > 5$, vị trí gần nhất là $5$.
- $i=7 (a_7=7)$: Bên trái có $a_5=8$ (vị trí 5) và $a_6=5$, vị trí gần nhất có giá trị lớn hơn 7 là $5$.

### 🏷 Subtasks

- Subtask 1 (30%): $N \le 10^3$.
- Subtask 2 (70%): $N \le 10^6$.

✅ Đã AC: 4 / 5 submissions