This article is participating in the nuggets team online activity, click to see the details

I. Title Description:

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

Example:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); –> return -3.minstack.pop (); minStack.top(); –> return 0. Minstack.min (); — — > to return to 2.

Note:

The total number of calls for each function does not exceed 20000 times.

Ii. Analysis of Ideas:

Implement a stack containing stack push, pop, min, top. You can see from this that you need to create a MinStack class that contains the above four methods.

The MIN function stack can be implemented using two stacks. One holds a stack of normal elements and the other holds a stack of smallest elements. The smallest element stack is arranged from largest to smallest.

Let’s pick the easy implementation first.

Top:

Return to the top of the stack. (this.element[this.element. Length-1])

Min:

The min method returns the smallest value in the current element stack. Simply return to the top of the smallest stack. (This.foot.length – 1)

Push:

For pushing, you can use a stack of elements to hold the normal order of elements.

Method one:

In the minimum stack,

  • The minimum stack is empty. Push the current element directly onto the minimum stack;
  • If the value is not empty, determine the current value stored and the top element of the current minimum stack: less than or equal to, perform the stack pressing operation.

Ex. :

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

Method 2: The minimum stack length is the same as the element stack.

  • The minimum stack is empty. Push the current element directly onto the minimum stack;
  • The minimum stack is not empty. If the current element is less than or equal to the top element of the minimum stack, the current element is pushed into the minimum stack. Greater than, the current minimum top element of the stack is pushed again.

Ex. :

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

Pop:

Method one:

After using push method I, it is necessary to determine whether the current minimum stack top is equal to the top element of the current element when considering the removal of the stack. If they are equal, the smallest stack needs to be unstacked when the elements are unstacked. Ex. :

minStack.pop();

minStack.pop();

Method 2: Use push method 2: when the element is pushed out of the stack, because the length of the smallest stack and the element stack is the same, the corresponding operation of the smallest stack can be carried out.

Ex. :

minStack.pop();

minStack.pop();

Iii. AC Code:

/ / method
class MinStack {
    element: number[];
    smallest: number[];
    constructor() {
        this.element = [];
        this.smallest = [];
    }
    push(x: number) :void {
        this.element.push(x);
        if (!this.smallest.length) {
            this.smallest.push(x);
        } else {
            if (this.smallest[this.smallest.length - 1] >= x) {
                this.smallest.push(x);
            }
        }
    }

    pop(): void {
        this.smallest[this.smallest.length - 1= = =this.element.pop() && this.smallest.pop();
    }

    top(): number {
        return this.element[this.element.length - 1];
    }

    min(): number {
        return this.smallest[this.smallest.length - 1]; }}2 / / method
push(num: number) {
    this.element.push(num);
    if (!this.smallest.length) {
      this.smallest.push(num);
    } else if (this.smallest[this.smallest.length - 1] >= num) {
      this.smallest.push(num);
    } else {
      this.smallest.push(this.smallest[this.smallest.length - 1]); }}pop() {
    this.element.pop();
    this.smallest.pop();
  }
Copy the code

Iv. Summary:

Examine the basic implementation function of the stack. This topic belongs to the simple topic, for stack principle understanding, basic can be made.