समस्या
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.
सीमाएँ
1 ≤ number of operations ≤ 200,000
0 ≤ x ≤ 10^9
उदाहरण
इनपुट:
operations = ["push 5", "push 3", "min", "pop", "min"]
अपेक्षित आउटपुट:
expected = [3, 5]इनपुट:
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};
अपेक्षित आउटपुट:
std::vector<long long> expected = {3, 5};इनपुट:
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};
अपेक्षित आउटपुट:
long[] expected = new long[] {3, 5};व्याख्या
With 5 and 3 on the stack the minimum is 3. After popping 3, only 5 is left: [3, 5].
इनपुट:
operations = ["min", "pop", "push 7", "min"]
अपेक्षित आउटपुट:
expected = [-1, 7]इनपुट:
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};
अपेक्षित आउटपुट:
std::vector<long long> expected = {-1, 7};इनपुट:
string[] operations = new string[] {"min", "pop", "push 7", "min"};
अपेक्षित आउटपुट:
long[] expected = new long[] {-1, 7};व्याख्या
The empty stack reports -1 and the pop is ignored; then the minimum is 7: [-1, 7].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Store, next to each value, the minimum of the stack at that point.
संकेत 2
The current minimum is then simply the top of that second stack.
संकेत 3
Ignore pop on an empty stack, and answer -1 for min when it is empty.
अपेक्षित जटिलता
O(number of operations) time, O(number of operations) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।