Encuentre el valor mayor más cercano para cada elemento en la 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, 6, 20, 12} 
Salida: 11 6 12 10 -1 20
Entrada: arr[] = {10, 5, 11, 10, 20, 12} 
Salida: 11 10 12 11 -1 20 
 

Una solución simple es ejecutar dos bucles anidados. Elegimos un elemento externo uno por uno. Para cada elemento seleccionado, recorremos la array restante y encontramos el elemento mayor 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 de autoequilibrio, podemos realizar operaciones tanto de inserción como más cercanas en tiempo O (Log n).
 

// C++ program to find closest greater value
// for every array element
#include <bits/stdc++.h>
using namespace std;
 
void closetGreater(int arr[], int n)
{
    // Insert all array elements into a Set
    set<int> ts;
    for (int i = 0; i < n; i++)
        ts.insert(arr[i]);
 
    // Find smallest greater element for
    // every array element
    for (int i = 0; i < n; i++)
    {
        auto greater = ts.upper_bound(arr[i]);
 
        if (greater == ts.end())
            cout << -1 << " ";
        else
            cout << *greater << " ";
    }
}
 
// Driver code
int main(int argc, char const *argv[])
{
    int arr[] = {10, 5, 11, 10, 20, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
    closetGreater(arr, n);
    return 0;
}
 
// This code is contributed by
// sanjeev2552

// Java program to find closest greater value for
// every array element
import java.util.*;
 
class TreeSetDemo {
    public static void closestGreater(int[] arr)
    {
        // Insert all array elements into a TreeSet
        TreeSet<Integer> ts = new TreeSet<Integer>();
        for (int i = 0; i < arr.length; i++)
            ts.add(arr[i]);
 
        // Find smallest greater element for every
        // array element
        for (int i = 0; i < arr.length; i++) {
            Integer greater = ts.higher(arr[i]);
            if (greater == null)
                System.out.print(-1 + " ");
            else
                System.out.print(greater + " ");
        }
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 10, 5, 11, 10, 20, 12};
        closestGreater(arr);
    }
}

# Python program to find closest greater value
# for every array element
def upper_bound(s, val):
    temp = list(s).copy()
    temp.sort()
    try:
        index_value = temp.index(val)
        if(index_value == len(temp)-1):
            return 0
        return temp[index_value+1]
    except ValueError:
        return arr[0]
 
def closetGreater(arr, n):
    # Insert all array elements into a Set
    ts = set()
    for i in range(n):
        ts.add(arr[i])
 
    # Find smallest greater element for
    # every array element
    for i in range(n):
        greater = upper_bound(ts, arr[i])
 
        if (greater == 0):
            print(-1,end = " ")
        else:
            print(greater,end = " ")
     
# Driver code
arr = [10, 5, 11, 10, 20, 12]
n = len(arr)
closetGreater(arr, n)
 
 
# This code is contributed by shinjanpatra

// C# program to find closest greater value for
// every array element
using System;
using System.Collections.Generic;
 
public class TreeSetDemo {
  public static void closestGreater(int[] arr)
  {
     
    // Insert all array elements into a TreeSet
    SortedSet<int> ts = new SortedSet<int>();
    for (int i = 0; i < arr.Length; i++)
      ts.Add(arr[i]);
 
    // Find smallest greater element for every
    // array element
    for (int i = 0; i < arr.Length; i++) {
      int greater = upper_bound(ts, arr[i]);
      if (greater == -1)
        Console.Write(-1 + " ");
      else
        Console.Write(greater + " ");
    }
  }
  public static int upper_bound(SortedSet<int> s, int val)
  {
    List<int> temp = new List<int>();
    temp.AddRange(s);
    temp.Sort();
    if (temp.IndexOf(val) + 1 == temp.Count)
      return -1;
    else
      return temp[temp.IndexOf(val) + 1];
  }
  public static void Main(String[] args)
  {
    int[] arr = { 10, 5, 11, 10, 20, 12 };
    closestGreater(arr);
  }
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript program to find closest greater value
// for every array element
 
function closetGreater(arr, n) {
    // Insert all array elements into a Set
    let ts = new Set();
    for (let i = 0; i < n; i++)
        ts.add(arr[i]);
 
    // Find smallest greater element for
    // every array element
    for (let i = 0; i < n; i++) {
        let greater = upper_bound(ts, arr[i]);
 
        if (!greater)
            document.write(-1 + " ");
        else
            document.write(greater + " ");
    }
}
 
function upper_bound(s, val) {
    let temp = [...s];
    temp.sort((a, b) => a - b);
    return temp[temp.indexOf(val) + 1];
}
 
// Driver code
 
let arr = [10, 5, 11, 10, 20, 12];
let n = arr.length;
closetGreater(arr, n);
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

11 10 12 11 -1 20

Complejidad de tiempo: O (n Log n)