arrays - übergeben - Ersetzen Sie in einem unsortierten Array jedes Element durch das erste größere Element auf der rechten Seite




c zweidimensionales array (2)

Die Grundidee ist, das Array in umgekehrter Reihenfolge (von rechts nach links) zu bearbeiten. Wir machen ein paar Beobachtungen:

  • Wenn wir gerade den Index i , k> j> i und A[k] ≤ A[j] , dann nennen wir element k irrelevant, weil es nie das Ergebnis für eines der Elemente 1, 2, ... ist. , k
  • Die relevanten Elemente rechts eines Indexes bilden daher eine monoton streng wachsende Teilfolge von A[i+1..n-1] .

In Ihrem Beispiel wären die Folgen relevanter Elemente von rechts nach links:

       []    
      [8]
    [4,8]
      [9]
    [5,9]
  [2,5,9]
  [1,5,9]

Es sieht wie ein Stapel aus, und wir können tatsächlich einen Stapel verwenden, um diese Sequenz zwischen Iterationen aufrechtzuerhalten.

Bei der Verarbeitung eines neuen Elements müssen wir zuerst das Ergebnis für das Array-Element finden. Die Beobachtung ist, dass das Ergebnis das oberste Element auf dem Stapel ist, das durch das neue Element nicht ungültig gemacht wird. Daher können wir alle Elemente, die irrelevant geworden sind, einfach aus dem Stapel entfernen. Was dann oben ist, ist unser Ergebnis. Wir können dann das neue Element vorantreiben, weil es nach unserer Definition relevant ist.

stack = []
A = [3, 1, 2, 5, 9, 4, 8]
result = [-1]*len(A)
for i := len(A) - 1 to 0:
    # remove all elements made irrelevant by A[i]
    while not stack.empty() && stack.top() <= A[i]:
        stack.pop()
    # now the top of the stack is the result for index i
    if not stack.empty():
        R[i] = stack.top()
    # push the new element on the stack. The stack will still contain all relevant 
    # elements in increasing order from top to bottom
    stack.push(A[i])

Die Schleifeninvariante für Iteration i ist " stack enthält die Subsequenz der relevanten Elemente rechts vom Index i ". Es ist leicht zu überprüfen und impliziert die Richtigkeit dieses Algorithmus.

Jedes Element wird höchstens einmal gepusht und gepoppt, sodass wir eine Gesamtlaufzeit von Ο (n) haben .

In einem unsortierten Array müssen wir jedes Element durch das erste Element rechts ersetzen, das größer ist als das aktuelle Element. Wenn keines der Elemente auf der rechten Seite größer ist, sollte es durch -1 .

Beispiel:

3  1  2  5  9  4  8   should be converted to
5  2  5  9 -1  8 -1

Ich kann mir die triviale Lösung vorstellen, bei der wir jedes Element mit dem gesamten Array überprüfen, das eine Ο (n²) Lösung ist. Gibt es einen besseren Weg, dies zu tun?


Sie können einen Stapel verwenden und die Zeitkomplexität ist O(N) .

algo: Beginne von der linken Seite und bewege dich nach rechts. Wenn Sie ein Element aus dem Array auswählen (sagen wir x), wird der Stapel so lange geöffnet, bis die Elemente aus dem Stack (also y) ein Element größer als das Array-Element haben, also x> y. Dann drücken Sie das Element, zB x, um zu stapeln.

zB {40,50,11,32,55,68,75} . hier ist s stapel.

40, wie s leer ist, drücken Sie es. s: 40

50, wie peek () <50 so pop 40 (40 ist das größere Element ist 50) als 50 drücken. s: 50

Nächstes höheres Element von 40 - 50.

11, s.peek ()> 11 so drücken Sie 11. s: 50, 11

32, s.peek () <32, so pop das Element und jetzt ist es 50, was größer ist als 32 und drücken Sie daher 32. s: 50 ,32

Nächstes höheres Element von 11 - 32.

55, s.peek () <55, so pop das Element dh 32 als Pop als nächstes sowie 50 <55, als 55 drücken. s: 55 .

Nächstes höheres Element von 32 - 55.

Nächstes höheres Element von 50 - 55.

68, speek () <68 so pop und drücken Sie 68. s: 68

75, speek () <75 so Pop und 75 s:75 drücken s:75 .

Nächstes höheres Element von 68 - 75.

Da das Array kein Element enthält, wird der Stapel einfach so aufgerufen, dass für alle Elemente innerhalb des Arrays kein größeres Element, dh -1, vorhanden ist.

Nächstes höheres Element von 75 - -1.

Derselbe Algo im Code:

public static void fun(int[] a) {
    Stack<Integer> s = new Stack<Integer>();
    s.push(a[0]);

    for (int i = 1; i < a.length; i++) {
        if (s.peek() != null) {
            while (true) {
                if (s.peek() == null || s.peek() > a[i]) {
                    break;
                }
                System.out.println(s.pop() + ":" + a[i]);
            }
        }
        s.push(a[i]);
    }
    while (s.peek() != null) {
        System.out.println(s.pop() + ":" + -1);
    }
}






time-complexity