Giá trị gần nhất nhỏ hơn
Đề bài
Cho một mảng gồm $n$ số nguyên, nhiệm vụ của bạn là với mỗi vị trí của mảng, tìm vị trí gần nhất bên trái của nó mà có giá trị nhỏ hơn, tìm vị trí gần nhất bên phải của nó mà có giá trị nhỏ hơn.
Input:
- Dòng đầu tiên có một số nguyên $n$: kích thước của mảng với $1 \le n \le 2 \cdot 10^5$.
- Dòng thứ hai có $n$ số nguyên $x_1, x_2, \ldots, x_n$: các giá trị của mảng với $1 \le x_i \le 10^9$.
Output: gồm 2 dòng:
- Dòng đầu tiên: in $n$ số nguyên – vị trí gần nhất bên trái nhỏ hơn cho mỗi vị trí trong mảng. Nếu không có, in $0$.
- Dòng thứ 2: in $n$ số nguyên – vị trí gần nhất bên phải nhỏ hơn cho mỗi vị trí trong mảng. Nếu không có, in giá trị $n + 1$.
Subtask:
- $20\%$ số test đầu tiên có $N \le 10^2$;
- $10\%$ số test tiếp theo có $N \le 10^3$;
- $10\%$ số test tiếp theo có $N \le 10^4$;
- $10\%$ số test tiếp theo có $N \le 10^5$;
- $50\%$ số test còn lại không có điều kiện gì thêm.
Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB.
8
2 5 1 4 8 3 2 50 1 0 3 4 3 3 7
3 3 9 6 6 7 9 9Giải thích ví dụ (vị trí đánh số từ 1): với $x_4 = 4$, đi sang trái gặp $x_3 = 1 < 4$ nên vị trí trái là $3$; đi sang phải $x_5 = 8$ không nhỏ hơn, $x_6 = 3 < 4$ nên vị trí phải là $6$. Với $x_3 = 1$ (nhỏ nhất mảng) thì bên trái không có → $0$, bên phải không có → $n + 1 = 9$. Chú ý: "nhỏ hơn" là nhỏ hơn hẳn – $x_7 = 2$ không tính $x_1 = 2$ là nhỏ hơn.
Lời mở đầu
Đây là bài kinh điển nhất của ngăn xếp đơn điệu (monotonic stack). Rất nhiều bài khó hơn – hình chữ nhật lớn nhất trong histogram, tích lớn nhất, đếm đoạn con có min/max cho trước... – đều dùng nó làm bước đầu tiên. Mình giải từ cách "đi từng bước" dễ hiểu tới ngăn xếp $O(n)$.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, chia đúng như subtask của đề:
| Test | n | Giá trị $x_i$ | Kiểu dãy |
|---|---|---|---|
| 1–10 | 2 … 10 | 1 … 30 | ngẫu nhiên |
| 11–20 | 100 | 3 … 32.753 | ngẫu nhiên |
| 21–30 | 1.000 | 2 … 32.767 | ngẫu nhiên |
| 31–40 | 10.000 | 1 … 32.768 | ngẫu nhiên |
| 41–50 | 100.000 | 1 … 32.768 | ngẫu nhiên |
| 51–70 | 200.000 | 1 … 200.000 | tăng dần |
| 71–90 | 200.000 | 1 … 200.000 | giảm dần |
| 91–100 | 200.000 | 1 … 100.001 | tăng rồi giảm |
- Các test 1–50 có giá trị ngẫu nhiên (đa số $\le 32\,768$), có lặp lại giá trị – nhớ dùng so sánh nhỏ hơn hẳn.
- 50 test lớn nhất ($n = 2 \cdot 10^5$) là các dãy "ác": tăng dần $1, 2, \ldots, n$ (test 51–70), giảm dần (test 71–90) và tăng rồi giảm hình ngọn núi $1, 2,$ $\ldots,$ $100\,001,$ $100\,000,$ $\ldots,$ $1$ (test 91–100). Đây chính là những dãy làm cách "đi từng bước" phải đi rất xa.
Kết quả chạy thật (giới hạn 1 giây):
| Subtask | Điều kiện | Test | Cách 1 (đi từng bước) | Cách 2 (ngăn xếp) |
|---|---|---|---|---|
| 1 (20%) | $N \le 10^2$ | 1–20 | 20/20 | 20/20 |
| 2 (10%) | $N \le 10^3$ | 21–30 | 10/10 | 10/10 |
| 3 (10%) | $N \le 10^4$ | 31–40 | 10/10 | 10/10 |
| 4 (10%) | $N \le 10^5$ | 41–50 | 10/10 | 10/10 |
| 5 (50%) | $N \le 2 \cdot 10^5$ | 51–100 | 0/50 | 50/50 |
Ý tưởngAi đứng sau và nhỏ hơn thì "che" người đứng trước
Xét bên trái. Giả sử đang ở vị trí $i$, và có hai vị trí $j < k < i$ với $x_j \ge x_k$. Khi đó $j$ không bao giờ là đáp án cho $i$ hay bất kỳ vị trí nào sau đó: nếu $x_j < x_i$ thì $x_k \le x_j < x_i$ và $k$ còn gần hơn. Nghĩa là $j$ đã bị $k$ che mất, có thể vứt bỏ.
Bên phải làm y hệt nhưng duyệt từ $n$ về $1$ (ngăn xếp rỗng thì đáp án là $n + 1$). Mỗi chỉ số được đẩy vào 1 lần và lấy ra tối đa 1 lần, nên mỗi lượt chỉ $O(n)$.
Em nhập dãy rồi bấm Tiếp để xem ngăn xếp chạy lượt trái rồi lượt phải:
Cách 1Đi sang trái, sang phải từng bước – $O(n^2)$
Cách tự nhiên nhất: với mỗi $i$, cho $j$ đi lùi từ $i - 1$ về $1$ cho tới khi gặp $a_j < a_i$; tương tự đi tiến từ $i + 1$ tới $n$. Nếu đi hết mảng thì $j$ dừng ở $0$ hoặc $n + 1$ – vừa khéo đúng giá trị đề yêu cầu in khi "không có".
- Vòng
while(j >= 1 && a[j] >= a[i]) j--;bỏ qua các số không nhỏ hơn $a_i$ (dấu>=vì cần nhỏ hơn hẳn). - Không cần xét riêng trường hợp "không có": vòng lặp tự dừng ở $j = 0$ (bên trái) hoặc $j = n + 1$ (bên phải).
- Với dãy ngẫu nhiên, $j$ thường dừng rất sớm. Nhưng với dãy tăng dần, mọi số phía sau đều lớn hơn nên vòng bên phải đi tới cuối mảng: tổng cộng $\approx n^2/2 = 2 \cdot 10^{10}$ bước.
Kết quả chạy thật: Bản C++ đúng 50/100 test, quá thời gian ở test 51–100; test đúng chạy lâu nhất 0.03s. Bản Python đúng 50/100 test, quá thời gian ở test 51–100; test đúng chạy lâu nhất 0.46s.
Cách 2Ngăn xếp đơn điệu – $O(n)$
Cài đặt đúng ý tưởng ở trên với stack<int> chứa chỉ số.
- Ngăn xếp chứa chỉ số chứ không chứa giá trị, vì đề hỏi vị trí; giá trị lấy qua
a[st.top()]. - Điều kiện pop là
a[st.top()] >= a[i]: các số bằng $a_i$ cũng bị bỏ, vì chúng không nhỏ hơn hẳn $a_i$ và từ nay đã bị $i$ che. - Sau vòng
while, ngăn xếp rỗng nghĩa là không có số nào bên trái nhỏ hơn → $0$; lượt phải thì → $n + 1$. - Trước lượt phải phải làm rỗng ngăn xếp (dòng
while(!st.empty()) st.pop();), nếu không sẽ dính chỉ số của lượt trái.
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.05s. Bản Python đúng 100/100 test; test đúng chạy lâu nhất 0.29s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Đi sang trái/phải từng bước | C++ | 50/100 | > 1s | Quá thời gian test 51–100 |
| Python | 50/100 | > 1s | Quá thời gian test 51–100 | |
| 2. Ngăn xếp đơn điệu | C++ | 100/100 | 0.05s | Full điểm |
| Python | 100/100 | 0.29s | Full điểm |
Nhận xét
Đăng nhận xét