This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

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.

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

Ii. Analysis of Ideas:

Array can be used to implement a stack is very simple, and to achieve linear time to the minimum, the first think of is the minimum pile, the problem is that this problem is to implement a stack, and to maintain the heap, using an array a pile of bad, because the heap is not convenient to delete a specified elements, each time a new heap on time, there is no advantage, So we write a brute force scheme that maintains two lists: stack,sort, and sort each time on and off the stack

Iii. AC Code:

var MinStack = function() {
    this.sort = [];
    this.stack = [];
};

MinStack.prototype.push = function(val) {
    this.stack.push(val);
    let index = this.sort.length;
    for(let i in this.sort){
        if (val<this.sort[i]){
            index = i;
            break;
        }
    }
    this.sort = [...this.sort.slice(0,index),val,...this.sort.slice(index,this.sort.length)];
};

MinStack.prototype.pop = function() {
    let popped = this.stack.pop();
    let i = this.sort.indexOf(popped);
    this.sort.splice(i,1);
};

MinStack.prototype.top = function() {
    return this.stack[this.stack.length-1]
};

MinStack.prototype.getMin = function() {
    return this.sort[0]
};
Copy the code

Iv. Summary:

As soon as AC looked at it, the time was really terrible. I would wait for the solution of the problem to make up the solution with low time complexity