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.

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) — Push element x onto stack.
  • pop() — Removes the element on top of the stack.
  • top() — Get the top element.
  • getMin() — Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(a); --> return -3.minstack.pop (); minStack.top(); --> return 0. Minstack.getmin(a); -- -- > to return to 2.Copy the code

Answer:

At first I thought I would just define a pointer to the minimum, but then IT occurred to me that when I pop an element on the stack, if the pop-up element is the minimum, that pointer needs to be changed to select another minimum element. No way, if you want to achieve the minimum time complexity of O(1), then you have to sacrifice space. You can create another stack to store data minimums in sequence.

Note: Python does not have a separate Stack data structure; instead, it has arrays that pop and push. You can also use collections.deque() data structures. In addition, it is necessary to determine whether the value is smaller than the value of the top element of the secondary stack when the data is pushed onto the stack. If it is smaller, it should also be added to the secondary stack. In addition, we need to determine whether the secondary stack is empty. Only when the secondary stack is not empty can we compare the top element of the stack; otherwise, overflow will occur.

The fact that you have to call a function every time to determine whether it is empty or not is very time-consuming, and can be avoided in this case by simply adding the maximum integer value to the secondary stack as the bottom element.

Java:

class MinStack {
    Stack<Integer> s1 = new Stack<>();// Initialize the stack
    Stack<Integer> s2 = new Stack<>();// Secondary stack order store minimum value

    public MinStack(a) {
        s2.push(Integer.MAX_VALUE);// Add the maximum integer value at the bottom of the stack to avoid determining whether the auxiliary stack is empty
    }

    public void push(int x) {
        s1.push(x);
        if (s2.peek() >= x) s2.push(x);// Add to the secondary stack if the value is less than or equal to the value of the top element
    }

    public void pop(a) {
        int tmp = s1.pop();
        if (tmp == s2.peek()) s2.pop();// If the value of an element on the secondary stack is equal to the value of the top element on the secondary stack, it will also be popped on the secondary stack
    }

    public int top(a) {
        return s1.peek();// Return the top element of the stack
    }

    public int getMin(a) {
        return s2.peek();// Returns the minimum at the top of the secondary stack}}Copy the code

Python3:

class MinStack:
	Initialize the data structure (array), s2 as the auxiliary stack to add the integer maximum as the stack bottom, avoid determining whether the auxiliary stack is empty
    def __init__(self):
        self.s1 = []
        self.s2 = []
        self.s2.append(sys.maxsize)

    def push(self, x: int) -> None:
        self.s1.append(x)
        Array[-1] = Array[-1]
        if self.s2[- 1] >= x: self.s2.append(x)

    def pop(self) -> None:
        tmp = self.s1.pop()
        if tmp == self.s2[- 1]: self.s2.pop()

    def top(self) -> int:
        return self.s1[- 1]

    def getMin(self) -> int:
        return self.s2[- 1]
Copy the code