Chương trình C++ tìm giá trị lớn hơn gần nhất cho mỗi phần tử mảng

Tìm giá trị lớn hơn gần nhất (next greater element) cho mỗi phần tử trong mảng. Nếu phần tử x có phần tử lớn hơn nó và có trong mảng, đó là giá trị lớn hơn gần nhất. Không có thì -1. Mảng [10,5,11,6,20,12] → [11,6,12,10,-1,20].

Dùng set C++ STL (cây nhị phân tìm kiếm). Inorder successor trong cây BST là phần tử lớn hơn gần nhất. Truy xuất O(log n).

Ví dụ mã nguồn

#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ả đầu ra

11 6 12 10 -1 20