Techo en el lado derecho para cada elemento de una array

Dada una array de enteros, encuentre el elemento mayor más cercano para cada elemento. Si no hay un elemento mayor, imprima -1
Ejemplos: 
 

Entrada: arr[] = {10, 5, 11, 10, 20, 12} 
Salida: 10 10 12 12 -1 -1
Entrada: arr[] = {50, 20, 200, 100, 30} 
Salida: 100 30 -1 -1 -1 
 

Una solución simple es ejecutar dos bucles anidados. Elegimos un elemento externo uno por uno. Para cada elemento seleccionado, recorremos la array del lado derecho y encontramos el elemento mayor o igual más cercano. La complejidad temporal de esta solución es O(n*n)
Una mejor solución es utilizar la clasificación. Ordenamos todos los elementos, luego, para cada elemento, avanzamos hacia la derecha hasta que encontramos un elemento mayor (Tenga en cuenta que puede haber múltiples ocurrencias de un elemento).
Una solución eficiente es usar Self Balancing BST (Implementado como se establece en C++ y TreeSet en Java ). En un BST Self Balancing, podemos realizar operaciones tanto de inserción como de techo en tiempo O(Log n).
 

// C++ program to find ceiling on right side for
// every element.
#include <bits/stdc++.h>
using namespace std;
 
void closestGreater(int arr[], int n)
{
    set<int> s;
    vector<int> ceilings;
 
    // Find smallest greater or equal element
    // for every array element
    for (int i = n - 1; i >= 0; i--) {
        auto greater = s.lower_bound(arr[i]);
        if (greater == s.end())
            ceilings.push_back(-1);
        else
            ceilings.push_back(*greater);
        s.insert(arr[i]);
    }
 
    for (int i = n - 1; i >= 0; i--)
        cout << ceilings[i] << " ";
}
 
int main()
{
    int arr[] = { 50, 20, 200, 100, 30 };
    closestGreater(arr, 5);
    return 0;
}

// Java program to find ceiling on right side for
// every element.
import java.util.*;
 
class TreeSetDemo {
    public static void closestGreater(int[] arr)
    {
        int n = arr.length;
        TreeSet<Integer> ts = new TreeSet<Integer>();
        ArrayList<Integer> ceilings = new ArrayList<Integer>(n);
 
        // Find smallest greater or equal element
        // for every array element
        for (int i = n - 1; i >= 0; i--) {
            Integer greater = ts.ceiling(arr[i]);
            if (greater == null)
                ceilings.add(-1);
            else
                ceilings.add(greater);
            ts.add(arr[i]);
        }
 
        for (int i = n - 1; i >= 0; i--)
            System.out.print(ceilings.get(i) + " ");
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 50, 20, 200, 100, 30 };
        closestGreater(arr);
    }
}

// C# program to find ceiling on right side for
// every element.
using System;
using System.Collections.Generic;
 
public class TreeSetDemo {
  public static void closestGreater(int[] arr)
  {
    int n = arr.Length;
    SortedSet<int> ts = new SortedSet<int>();
    List<int> ceilings = new List<int>(n);
 
    // Find smallest greater or equal element
    // for every array element
    for (int i = n - 1; i >= 0; i--) {
      int greater = lower_bound(ts, arr[i]);
      if (greater == -1)
        ceilings.Add(-1);
      else
        ceilings.Add(greater);
      ts.Add(arr[i]);
    }
    ceilings.Sort((a,b)=>a-b);
    for (int i = n - 1; i >= 0; i--)
      Console.Write(ceilings[i] + " ");
  }
  public static int lower_bound(SortedSet<int> s, int val)
  {
    List<int> temp = new List<int>();
    temp.AddRange(s);
    temp.Sort();
    temp.Reverse();
 
    if (temp.IndexOf(val) + 1 == temp.Count)
      return -1;
    else if(temp[temp.IndexOf(val) +1]>val)
      return -1;
    else
      return temp[temp.IndexOf(val) +1];
  }
 
  public static void Main(String[] args)
  {
    int[] arr = { 50, 20, 200, 100, 30 };
    closestGreater(arr);
  }
}
 
// This code is contributed by Rajput-Ji

100 30 -1 -1 -1

Complejidad de tiempo: O (n Log n)