Finden Sie das nächste größere Element in einem Array

Question

Gegeben ein Array, für jedes Element muss ich das kleinste Element auf der rechten Seite des gegebenen Elements finden, das größer als das aktuelle Element ist.

Mathematisch Für jeden Index i in Array A, ich brauche Index j so dass

A[j] > A[i] 
j > i 
A[j] - A[i] is minimum 

I ji

Die Brute-Force-Lösung für jeden Index wäre zu finden Nötige zu finden, O(n^2) und ich hoffe, es besser zu machen. Ich denke, dass eine O(n log n) Lösung mit selbstausgleichenden BST möglich ist, aber das scheint ziemlich komplex. Außerdem brauche ich eine O(n) Lösung.

Gibt es eine O(n) Lösung für dieses Problem? Gibt es einen Beweis, dass die untere Grenze O(n log n) ist?

Answer 1

Nachweis von O (n log n) untere Schranke: (zum Vergleich basierte Algorithmen)

Lets sagen, dass wir einen Vergleich basierten Algorithmus, der diese Aufgabe in O erreichen würde (n). Das heißt, für jeden Index haben wir das unmittelbar größere Element zu seiner Rechten (sagen wir R [i]).

In ähnlicher Weise können wir diesen Algorithmus auf dem umgekehrten Eingabearray ausführen und dann das Ergebnis umkehren. Für jeden Index haben wir das unmittelbar größere Element zu seiner Linken (sagen wir L [i]).

Das bedeutet, dass wir in O (n) für jedes Element das unmittelbar größere Element im Array = min (R [i], L [i]) haben.

Wir können jetzt das Array mit diesen Informationen sortieren.

Suchen Sie das minimale Element im Array. Finden Sie den Nachfolger (unmittelbares größeres Element), dann den Nachfolger des Nachfolgers usw. Damit hätten Sie das gesamte Array in sortierter Reihenfolge erhalten.

Sortierte das Array in O (n) nur mit Vergleichen (ein Widerspruch).

O (n log n) Algorithmus:
Starten der ausgeglichene BST von rechts der Anordnung aufzubauen. Die Knoten würden die Werte und die entsprechenden Indizes enthalten.

Dann würde für jedes neue gefundene Element das Einfügen in die BST den entsprechenden nächstgrößeren Index/Wert erhalten.