Heim > Java > javaLernprogramm > So verwenden Sie einen monotonen Stapel in Java

So verwenden Sie einen monotonen Stapel in Java

WBOY
Freigeben: 2023-05-17 10:07:05
nach vorne
1159 Leute haben es durchsucht

1. Das nächste größere Element

Problembeschreibung

So verwenden Sie einen monotonen Stapel in Java

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

So verwenden Sie einen monotonen Stapel in Java

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. So verwenden Sie einen monotonen Stapel in Java

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

So verwenden Sie einen monotonen Stapel in Java

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.

So verwenden Sie einen monotonen Stapel in JavaCode 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;
    }
}
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:yisu.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage