Problem
A generic Stack<T> works for any type. Here you extend the idea: a stack of integers that can also report its minimum in constant time.
Process the operations in order:
push <x>: push x.pop: remove the top value (ignored when the stack is empty).min: report the smallest value currently in the stack, or -1 if it is empty.
Implement min_stack_operations(operations).
Input
operations: The operations.
Output
Return the answers of the min operations, in order.
Einschränkungen
1 ≤ number of operations ≤ 200,000
0 ≤ x ≤ 10^9
Beispiele
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
With 5 and 3 on the stack the minimum is 3. After popping 3, only 5 is left: [3, 5].
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
The empty stack reports -1 and the pop is ignored; then the minimum is 7: [-1, 7].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Store, next to each value, the minimum of the stack at that point.
Hinweis 2
The current minimum is then simply the top of that second stack.
Hinweis 3
Ignore pop on an empty stack, and answer -1 for min when it is empty.
Erwartete Komplexität
O(number of operations) time, O(number of operations) extra space
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.