Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Minimum stack

Topic describes

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.

Example:

Input: [” MinStack “, “push” and “push” and “push” and “getMin”, “pop”, “top”, “getMin”] [[], [2], [0], [3], [], [], [], []]

Output: [, null, null, null, null, null, 0, 2)

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.

Tip:

Pop, top, and getMin operations are always called on a non-empty stack.

Thinking a

  • Normal stack data structure, implementationgetMinMethod must traverse all the elements in the stack and find the minimum value, where the time complexity is zeroO(n)And they want it to be in constant time, which is the time complexityO(1)In the implementation.
  • The time complexity of reading the top of the stack isO(1), can use the second auxiliary stack, the top of the auxiliary stack to save the current stack minimum, callgetMinMethod, read directly to the top of the auxiliary stack.

Code implementation

var MinStack = function() {
  this.stackArr = [] // Save all data stacks
  this.minStackArr = [] // Save the minimum helper stack
};

/ * * *@param {number} val
 * @return {void}* /
MinStack.prototype.push = function(val) {
    this.stackArr.push(val)
    // When the secondary stack is empty, also push the first value, set to the current minStack minimum
    // Each subsequent push will be pushed to the top of the auxiliary stack if it is smaller, otherwise no operation will be performed
    if (this.minStackArr.length === 0 || val <= this.minStackArr[this.minStackArr.length - 1]) {this.minStackArr.push(val)
    }
};

/ * * *@return {void}* /
MinStack.prototype.pop = function() {
    let item = this.stackArr.pop()
    // If the value is equal to the top value of the secondary stack, the secondary stack is also removed to keep the current minimum value
    if (item === this.minStackArr[this.minStackArr.length - 1]) {
        this.minStackArr.pop()
    }
};

/ * * *@return {number}* /
MinStack.prototype.top = function() {
    return this.stackArr[this.stackArr.length - 1]};/ * * *@return {number}* /
MinStack.prototype.getMin = function() {
    return this.minStackArr[this.minStackArr.length - 1]};/** * 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

Idea 2

  • Idea one is to create a new stack to maintain the minimum stack
  • Idea 2 can be implemented the other way, on the same stack. Where eachpushThe current stack minimum can be maintained in addition to the original data, for example{val, minVal}. That is, one stack element holds two values. Before each stack pressing, judge the minimum value at the top of the current stack and the value of the new data. If the value of the new data is smaller, the stack is pushed and the minimum value of the current stack is updated.
    • First push: [{val: -2, minVal: -2}], => Current minimum value -2
    • The second pressure stack: [{val: – 2, minVal: – 2}, {val: 0, minVal: – 2}] = > the current minimum – 2
    • Third pressure stack: [{val: – 2, minVal: – 2}, {val: 0, minVal: – 2}, {val: – 3, minVal: – 3}] = > the current minimum – 3

Code implementation

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

/ * * *@param {number} val
* @return {void}* /
MinStack.prototype.push = function(val) {
   if (this.stackArr.length === 0 || val < this.stackArr[this.stackArr.length -1].minVal) {
       this.stackArr.push({
           val: val,
           minVal: val
       })
   } else {
       this.stackArr.push({
           val: val,
           minVal: this.stackArr[this.stackArr.length -1].minVal
       })
   }
};

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

/ * * *@return {number}* /
MinStack.prototype.top = function() {
   return this.stackArr[this.stackArr.length - 1].val
};

/ * * *@return {number}* /
MinStack.prototype.getMin = function() {
   return this.stackArr[this.stackArr.length - 1].minVal
};

/**
* 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

Scheme comparison

  • Based on the commit results, the time and memory consumption of both solutions are similar
  • From the point of view of the code, in addition to the second way to push the stack, other methods and normal stack call method, more concise