Đề bài
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.
Ràng buộc
1 ≤ number of operations ≤ 200,000
0 ≤ x ≤ 10^9
Ví dụ
Đầu vào:
operations = ["push 5", "push 3", "min", "pop", "min"]
Kết quả mong đợi:
expected = [3, 5]Đầu vào:
std::vector<std::string> operations = {"push 5", "push 3", "min", "pop", "min"};
Kết quả mong đợi:
std::vector<long long> expected = {3, 5};Đầu vào:
string[] operations = new string[] {"push 5", "push 3", "min", "pop", "min"};
Kết quả mong đợi:
long[] expected = new long[] {3, 5};Giải thích
With 5 and 3 on the stack the minimum is 3. After popping 3, only 5 is left: [3, 5].
Đầu vào:
operations = ["min", "pop", "push 7", "min"]
Kết quả mong đợi:
expected = [-1, 7]Đầu vào:
std::vector<std::string> operations = {"min", "pop", "push 7", "min"};
Kết quả mong đợi:
std::vector<long long> expected = {-1, 7};Đầu vào:
string[] operations = new string[] {"min", "pop", "push 7", "min"};
Kết quả mong đợi:
long[] expected = new long[] {-1, 7};Giải thích
The empty stack reports -1 and the pop is ignored; then the minimum is 7: [-1, 7].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Store, next to each value, the minimum of the stack at that point.
Gợi ý 2
The current minimum is then simply the top of that second stack.
Gợi ý 3
Ignore pop on an empty stack, and answer -1 for min when it is empty.
Độ phức tạp mong đợi
O(number of operations) time, O(number of operations) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.