Cho mảng, tìm phần tử lớn hơn gần nhất (closest greater) cho mỗi phần tử. Nếu không có trả về -1. Ví dụ [10,5,11,6,20,12] → [11,6,12,10,-1,20].
Dùng set C++ STL (cây nhị phân). In-order successor là phần tử lớn hơn gần nhất. Truy xuất O(log n).
Ví dụ
#include<iostream> #include<set> using namespace std; void nearestGreatest(int arr[], int n) { set<int> tempSet; for (int i = 0; i < n; i++) tempSet.insert(arr[i]); for (int i = 0; i < n; i++) { auto next_greater = tempSet.upper_bound(arr[i]); if (next_greater == tempSet.end()) cout << -1 << " "; else cout << *next_greater << " "; } } int main() { int arr[] = {10, 5, 11, 6, 20, 12}; int n = sizeof(arr) / sizeof(arr[0]); nearestGreatest(arr, n); }
Kết quả
11 6 12 10 -1 20