Refer to Offer 30. Stack containing min function

The question

Refer to Offer 30. Stack containing min function

solution

This problem is mainly concerned with how to maintain the location of the smallest element.

When it comes to pushing, it’s a simple case. If you swap, it must be the element being pushed

The situation is complicated when unstacking, because if the unstacking element is the smallest element, you need to find out where the second-smallest element updates the smallest element. Here we use the method of iterating through the remaining elements to find the smallest element.

Optimization: Compare the out of stack element with the smallest element when out of stack. If unstack element > minimum element, the position of the minimum element remains unchanged and the traversal process is skipped. If the off-stack element = the smallest element, then you need to iterate to get the smallest element of the remaining elements.

code

/** * initialize your data structure here. */
 var MinStack = function() {
    this.arr = []                   // Use arrays to simulate stacks
    this.stackTop =  0              // Record the top position of the stack
    this.minIndex = 0               // Record the position of the smallest element
};

/ * * *@param {number} x
 * @return {void}* /
MinStack.prototype.push = function(x) {
    this.arr[this.stackTop++] = x
    
    // Update the position of the smallest element on the stack
    if(x<this.arr[this.minIndex])this.minIndex = this.stackTop-1
};

/ * * *@return {void}* /
MinStack.prototype.pop = function() {
    if (this.stackTop > 0) {
    this.stackTop--;
    
    // Update the position of the smallest element as it exits the stack
    if (this.stackTop === 0) {
      this.minIndex = 0;
    } else {
    
    // If the stack is not empty, iterate to get the position of the smallest element
      let tep = 0;
      for (let i = 0; i < this.stackTop; i++) {
        if (this.arr[i] < this.arr[tep]) {
          tep = i
          
        }
      }
      this.minIndex = tep
    }
  }
  return null;
};

/ * * *@return {number}* /
MinStack.prototype.top = function() {
    return this.arr[this.stackTop-1]};/ * * *@return {number}* /
MinStack.prototype.min = function() {
    return this.stackTop===0?undefined:this.arr[this.minIndex]

};

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

Refer to Offer 30. Stack containing min function