So verwenden Sie einen monotonen Stapel in Java

1. Das nächste größere Element

Problembeschreibung

Detaillierte Erklärung der Ideen

Diese Frage verwendet eine gewalttätigere Lösung.

Wir initialisieren zunächst ein res-Array mit der gleichen Länge wie nums, um die Ergebnisse zu speichern. Wir durchlaufen die Werte in nums und suchen in nums2, bis wir nums2[j] == nums[i] finden. Wir beginnen dann mit j von nums2. Dann durchqueren wir, um ein Array zu finden, das größer als nums[i] ist, und geben es zurück

Problembeschreibung

Detaillierte Erläuterung der Idee

Auch diese Frage verwendet eine relativ heftige Methode. Dasselbe wie bei der vorherigen Frage.

Doppelte Schleife, offensichtlich ist diese Methode zeitlich komplexer. Auch hier wird eine Methode mit geringerer Zeitkomplexität bereitgestellt.

Monotoner Stapel

Was wir pflegen, ist ein Lückenarray, das das Ergebnisarray ist. Erstellen Sie zunächst einen Stapel und stellen Sie fest, ob der Stapel leer ist. Wenn er nicht leer ist, legen Sie ihn fest. Vergleichen Sie das oberste Element des Stapels mit dem aktuellen Element. Wenn das aktuelle Element größer als das aktuelle Element ist, wird die Differenz in das entsprechende Ergebnisarray eingefügt und das oberste Element des Stapels entfernt Das Ergebnisarray wird auf den Stapel verschoben.

Hier ist ein Link zur Animation. Es ist eine gute Idee, den monotonen Stapel in der Animation zu lernen.

Code und Ergebnisse

3. Das nächste größere Element II

Problembeschreibung

Detaillierte Idee

Die Idee dieser Frage ist ein monotoner Stapel. Frage 1 wird gewaltsam gelöst. Diese Frage erfordert die Verwendung eines monotonen Stapels.

Das Prinzip ist das gleiche wie bei der zweiten Frage, achten Sie nur auf die Schleife. Gehen Sie direkt zum Code. Wenn Sie damit nicht vertraut sind, können Sie sich das Video der zweiten Frage ansehen und es sich dann ansehen.

Code und Ergebnisse

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] res = new int[m];
        for (int i = 0; i < m; ++i) {
            int j = 0;
            while (j < n && nums2[j] != nums1[i]) {
                ++j;
            }
            int k = j + 1;
            while (k < n && nums2[k] < nums2[j]) {
                ++k;
            }
            res[i] = k < n ? nums2[k] : -1;
        }
        return res;
    }
}

Das obige ist der detaillierte Inhalt vonSo verwenden Sie einen monotonen Stapel in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!