Mittel 0 gelöst 0% Erfolgsquote

Min-Stack

Baue einen Stack, der nach jedem Push oder Pop sofort sein kleinstes Element meldet.

Das lernst du

  • Das Minimum bei jedem Push mitspeichern
  • Min-Abfragen in konstanter Zeit beantworten
  • Pop auf einem leeren Stack sicher behandeln

Problem

Ein generic Stack<T> funktioniert für jeden Typ. Hier erweiterst du die Idee: ein Stack von Ganzzahlen, der auch sein Minimum in konstanter Zeit melden kann.

Verarbeite die Operationen in Reihenfolge:

  • push <x>: x auf den Stack legen.
  • pop: den obersten Wert entfernen (wird ignoriert, wenn der Stack leer ist).
  • min: den kleinsten Wert melden, der sich aktuell im Stack befindet, oder -1, wenn er leer ist.

Implementiere min_stack_operations(operations).

Input

operations: Die Operationen.

Output

Gib die Antworten der min-Operationen in Reihenfolge zurück.

Einschränkungen

1 ≤ Anzahl der Operationen ≤ 200,000

0 ≤ x ≤ 10^9

Beispiele

Beispiel 1
Eingabe:
operations = ["push 5", "push 3", "min", "pop", "min"]

Erwartete Ausgabe:
expected = [3, 5]
Eingabe:
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};

Erwartete Ausgabe:
std::vector<long long> expected = {3, 5};
Eingabe:
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};

Erwartete Ausgabe:
long[] expected = new long[] {3, 5};

Erläuterung

Mit 5 und 3 auf dem Stack ist das Minimum 3. Nach dem Pop von 3 bleibt nur 5 übrig: [3, 5].

Beispiel 2
Eingabe:
operations = ["min", "pop", "push 7", "min"]

Erwartete Ausgabe:
expected = [-1, 7]
Eingabe:
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};

Erwartete Ausgabe:
std::vector<long long> expected = {-1, 7};
Eingabe:
string[] operations = new string[] {"min", "pop", "push 7", "min"};

Erwartete Ausgabe:
long[] expected = new long[] {-1, 7};

Erläuterung

Der leere Stack meldet -1 und der Pop wird ignoriert; dann ist das Minimum 7: [-1, 7].

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Speichere neben jedem Wert das Minimum des Stacks zu diesem Zeitpunkt.

Hinweis 2

Das aktuelle Minimum ist dann einfach das oberste Element dieses zweiten Stacks.

Hinweis 3

Ignoriere pop auf einem leeren Stack und antworte bei min dann mit -1.

Erwartete Komplexität

Zeit O(Anzahl der Operationen), zusätzlicher Speicher O(Anzahl der Operationen)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.