The topic of dry

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.

Source: LeetCode link: leetcode-cn.com/problems/mi… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution: Record the minimum stack

In fact, at first I got the problem and thought it was very easy, nothing more than to find the minimum value to return, but things are definitely not so simple. The efficiency is really not very high.

Therefore, we can set a special stack for the smallest stack, and set it to the top of the stack if the current val is less than the top element of the smallest stack, and vice versa, the top of the stack is still the minimum. So when we’re looking for the minimum, we just take the top element of the minimum stack. There is also concern about removing elements, which is that both stacks are removed at the same time, without causing confusion, because the current minimum top of the stack is either the top of our main stack. Or the element below the main stack.

Code implementation:

/** * initialize your data structure here. */
var MinStack = function () {
    this.stack = []
    this.minStack = [];
};

/ * * *@param {number} val
 * @return {void}* /
MinStack.prototype.push = function (val) {
    let length1 = this.stack.length;
    let length2 = this.minStack.length;
    if (length1 == 0 && length2 == 0) {
        this.stack.push(val)
        this.minStack.push(val)
    } else {
        if (this.minStack[length2 - 1] > val) {
            this.minStack.push(val)
            this.stack.push(val)
        } else {
            this.minStack.push(this.minStack[length2 - 1])
            this.stack.push(val)
        }
    }
};

/ * * *@return {void}* /
MinStack.prototype.pop = function () {
    this.minStack.pop();
    return this.stack.pop();
};

/ * * *@return {number}* /
MinStack.prototype.top = function () {
    return this.stack[this.stack.length - 1]};/ * * *@return {number}* /
MinStack.prototype.getMin = function () {
    return this.minStack[this.minStack.length - 1]
    // return Math.min(... this.stack)
};

/** * Your MinStack object will be instantiated and called as such: * var obj = new MinStack() * obj.push(val) * obj.pop() * var param_3 = obj.top() * var param_4 = obj.getMin() */
Copy the code