To define the data structure of the stack, implement a min function in this type that can obtain the smallest element of the stack. In this stack, the time complexity of calling min, push, and pop is O(1).

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3); minStack.min(); -- -- > returns3minStack.pop(); minStack.top(); - > to return0minStack.min(); -- -- > returns2
Copy the code

The difficulties in

  1. The operation time complexity of push and POP is O(1), and the time complexity of min function is, if it is implemented by sorting or searchingO(n)Is unable to complete the problem requirementsO(1)
  2. Define a minValue to save the minimum value, each time push, and minValue comparison, ensure that minValue is always the smallest element, when calling min function return minValue value. But if pop goes out at exactly the minimum, there’s no way to know what the next minimum is when you call min again.

Train of thought

This can be done with two stacks, a primary stack for data structures and a secondary stack for minimum values.

  • When the main stack element is pushed, the secondary stack stores the minimum value of the element in the stack
  • When the main stack element leaves the stack, the secondary stack element also leaves the stack
  • The minimum value is the top value of the auxiliary stack element
  • The top stack value is the top value of the main stack element

code

class Stack {
    constructor() {
        this.arr = []
    }

    add(value) {
        this.arr.push(value)
    }

    pop() {
        return this.arr.pop()
    }

    top() {
        const len = this.arr.length;
        if(len ! =0) {
            return this.arr[len - 1]}}empty() {
        return this.arr.length === 0}}class MinStack {
    constructor() {
        this.A = new Stack()   / / the main stack
        this.B = new Stack()   / / auxiliary stack
    }

    push(value) {
        this.A.add(value)
        if(this.B.empty()) {
            this.B.add(value)
        }else{
            this.B.add(value < this.B.top() ? value : this.B.top())
        }
    }

    min() {
        return this.B.top()   /// Return the minimum stack value
    }

    pop() {
        this.B.pop()
        return this.A.pop()    
    }

    top() {
        return this.A.top()   // Return the top value of the stack}}const minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
console.log(minStack.min());   / / return - 3
minStack.pop();
console.log(minStack.top());   / / returns 0
console.log(minStack.min());   / / return - 2
Copy the code

conclusion

In this article, we learned how to implement a stack with a min function, which is O(1) in time.

Use the main stack and auxiliary stack to realize min, the main stack storage data structure, auxiliary stack storage minimum value, the main stack and auxiliary stack simultaneously into the stack and out of the stack, keep the stack synchronization, the top of the main stack is the top value of the stack, the top of the auxiliary stack is the minimum value of the stack.

thinking

By means of auxiliary stack, the time complexity of min is O(1) to meet the requirement of understanding the problem. However, there are many continuous and repetitive elements in the auxiliary stack, which will occupy extra space of a master site. Can the storage of auxiliary stack be optimized?

can

  • When pushed, the secondary stack stores only the value smaller than the top of the secondary stack
  • When you go out of the stack, the main stack pops, if the minimum gets popped, the secondary stack has to synchronize with the main stack, and pop the minimum.
class MinStack {
    push(value) {
        this.A.add(value)
        if(this.B.empty() || value <= this.B.top()) {
            this.B.add(value)
        }
    }
    pop() {
        if(this.A.pop() === this.B.top()) {
            this.B.pop()
        }
    }
}
Copy the code