Ngăn xếp đơn điệu tìm phần tử lớn hơn đầu tiên bên phải
Hệ thống cảm biến đo đạc địa hình thực tế ảo của AI Empire Academy thu thập độ cao của N trạm radar đặt thẳng hàng từ trái sang phải: H1, H2, …, HN (1 ≤ N ≤ 2 · 105…
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: std stack, std vector, loops.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu và cài đặt kỹ thuật Ngăn xếp đơn điệu (Monotonic Stack).
- Giải quyết bài toán Next Greater Element (Phần tử lớn hơn đầu tiên bên phải) trong thời gian tối ưu tuyến tính O(N).
- Quản lý ngăn xếp lưu chỉ số (Index Stack) thay vì lưu giá trị.
- Tối ưu I/O cho dữ liệu lớn N = 2 · 105.
Mô tả bài toán
Hệ thống cảm biến đo đạc địa hình thực tế ảo của AI Empire Academy thu thập độ cao của N trạm radar đặt thẳng hàng từ trái sang phải: H1, H2, …, HN (1 ≤ N ≤ 2 · 105, 1 ≤ Hi ≤ 109).
Mỗi trạm radar thứ i phát tia quét ngang về phía bên phải. Tia quét sẽ bị chặn lại bởi trạm radar đầu tiên đứng sau nó có độ cao lớn hơn hẳn độ cao của nó (nghĩa là tìm chỉ số j > i nhỏ nhất sao cho Hj > Hi).
Với mỗi trạm radar i (1 ≤ i ≤ N):
- Hãy in ra chỉ số j (1-indexed) của trạm radar đầu tiên bên phải chặn tia quét của nó.
- Nếu không có trạm nào bên phải cao hơn nó, in ra
-1.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Dòng 1: Một số nguyên dương N (1 ≤ N ≤ 2 · 105).
- Dòng 2: Gồm N số nguyên dương H1, H2, …, HN cách nhau bởi dấu cách (1 ≤ Hi ≤ 109).
Output
In trên một dòng gồm N số nguyên cách nhau bởi dấu cách, số thứ i là chỉ số trạm chắn radar thứ i (hoặc -1).
Ràng buộc
- 1 ≤ N ≤ 2 · 105.
- 1 ≤ Hi ≤ 109.
- Thời gian chạy: 1000ms.
- Bộ nhớ tối đa: 256MB.
Ví dụ 1
Input
6
4 5 2 10 8 3Output
2 4 4 -1 -1 -1Giải thích
- Trạm 1 (H1 = 4): Trạm đầu tiên bên phải cao hơn là trạm 2 (H2 = 5 > 4) → in
2. - Trạm 2 (H2 = 5): Trạm đầu tiên bên phải cao hơn là trạm 4 (H4 = 10 > 5) → in
4. - Trạm 3 (H3 = 2): Trạm đầu tiên bên phải cao hơn là trạm 4 (H4 = 10 > 2) → in
4. - Trạm 4 (H4 = 10): Không có trạm nào bên phải cao hơn 10 → in
-1. - Trạm 5 (H5 = 8): Không có trạm nào bên phải cao hơn 8 → in
-1. - Trạm 6 (H6 = 3): Đứng cuối cùng, không có trạm bên phải → in
-1.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.