This is the second day of my participation in Gwen Challenge

Topic describes

Minimum stack

Design a stack that supports push, pop, and top operations and can retrieve the smallest element in constant time.

  • Push (x) – Pushes element X onto the stack.
  • Pop () — Removes the top element of the stack.
  • Top () — Gets the top element on the stack.
  • GetMin () — Retrieves the smallest element in the stack.

Example:

Input: [" MinStack ", "push" and "push" and "push" and "getMin", "pop", "top", "getMin"] [[], [2], [0], [3], [], [], [], []] output: [null,null,null,null,-3, NULL,0,-2] MinStack MinStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> return -3.minstack.pop (); minStack.top(); --> return 0. Minstack.getmin (); -- -- > to return to 2.Copy the code

Tip:

  • pop,top 和 getMinOperations are always inStack is not emptyOn the call.

Thought analysis

The time complexity of the push operation is O(n){O(n)}O(n), and the time complexity of the pop and top operation is O(1){O(1)}O(1). If we want to get the minimum value in the queue, we still need to traverse the queue and get the minimum value. So the time complexity is O(n){O(n)}O(n), and the problem requires that the minimum value be retrieved in constant time. Of course, we can also add an auxiliary queue to assist, or we can achieve the minimum value of constant time.

The time complexity of push, pop and top is constant, but the time complexity of obtaining the minimum value is O(n){O(n)}O(n) if the auxiliary queue is implemented, so we can consider adding a auxiliary stack to achieve it.

Each time a push operation is performed, the minimum value of the secondary stack is compared to the push value, and the minimum value is pushed to the secondary stack so that the top of the secondary stack is the minimum value.

So, to do this problem, we need to understand the nature of the stack. For a stack, if an element A is pushed onto the stack and there are other elements B, C, and D on the stack, then no matter what happens to the stack, as long as a is on the stack, B, C, and D must be on the stack, because before A is ejected, B, C, D will not be ejected.

So at any point in time, if the top element on the stack is A, then you can be certain that the current element on the stack must be a, B, C, and D.

We can store the minimum value of the current stack as each element a is pushed, and then whenever the top element a is, we can just return the minimum value of the stack.

The code shown

Solution: The time complexity of pop, top, push is O(1){O(1)}O(1), and the time complexity of getMin is O(1){O(1)}O(1).

class MinStack {

    /** initialize your data structure here. */
    Stack<Integer> assistStack = null;
    Stack<Integer> localStack = null;
    public MinStack(a) {
        assistStack = new Stack<>();
        localStack = new Stack<>();
        assistStack.push(Integer.MAX_VALUE);
    }

    public void push(int val) { / / 2, 1
        assistStack.push(Math.min(val,assistStack.peek()));
        localStack.push(val);
    }

    public void pop(a) {
        localStack.pop();
        assistStack.pop();
    }

    public int top(a) {
        return localStack.peek();
    }

    public int getMin(a) {
        returnassistStack.peek(); }}Copy the code

Since pop, top, and getMin operate on a non-empty stack, there is no need to make a non-empty judgment.

conclusion

If you want to simulate a minimum stack, it is best to simulate it with the stack itself, since the time complexity of the basic stack operations is O(1){O(1)}O(1), and then add a secondary stack for the minimum processing.