[Mảng 1 Chiều Cơ Bản]. Bài 42. Next greater element
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho mảng A[] gồm N phần tử, nhiệm vụ của bạn là đối với mỗi phần tử trong mảng A[] bạn hãy tìm phần tử đầu tiên lớn hơn nó nằm ở bên phải, đối với phần tử không có phần tử lớn hơn bên phải thì in ra -1
Ví dụ : mảng A[] là {3, 8, 9, 1, 4, 2, 5} thì kết quả sẽ là 8, 9, -1, 4, 5, 5, -1.
Gợi ý : Đối với mỗi chỉ số i sử dụng 1 vòng for từ i + 1 tới cuối dãy để tìm số đầu tiên lớn hơn A[i], tìm được thì break và in ra.
Đầu vào
Dòng 1 là N : số phần tử trong mảng
Dòng 2 là N phần tử cách nhau 1 khoảng trắng
Giới hạn
1<=N<=1000
0<=A[i]<=1000
Đầu ra
In ra đáp án của bài toán
Ví dụ :
Input 01
8
53 97 89 87 17 70 27 46
Output 01
97 -1 -1 -1 70 -1 46 -1
Bình luận
Có cách nào làm bài này nhanh hơn O(n*n) ko nhỉ mn
hay la thu luu max cua a[n-1] den a[i] trong mang f[n] di, chung nao can hoi if(a[i]!=f[i]) la dc,luu mang f ton co O(n) cong may thu khac nua thoi(khong biet dung hay sai nhung khong can 2 vong long nhau)
Cách bạn nói lưu max bên phải là sai bản chất bài toán nhé 'Next greater element' yêu cầu phần tử đầu tiên lớn hơn nằm bên phải, không phải max của đoạn sau dyệt từ phải sang và dùng stack đơn điệu mới là giải pháp O(n) đúng nhá
duyệt ngược từ n-2 đến 0 ấy bro, duy trì một biến max đến tìm giá trị max nằm bên phải a[i] , r so với a[i] th
xl tôi nhầm
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.