Finger Offer(23) – stack containing min function

“This is the 23rd day of my participation in the August Gwen Challenge.

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.

There are two ways to solve the problem, but the essence is the same: use two stacks. One stack is used to store the data pushed in, and the other stack is used to store the minimum value of the current stack. It can dynamically update the minimum value of the current stack as the data is pushed in and out. The first method uses two stacks, data_stack and min_stack. The top of min_stack is the minimum value corresponding to the current data stack. Pushing rule: For data value to be pushed, the number is first pushed onto data_stack. If value<=min_stack.top(), push the number into the min_stack, otherwise push the corresponding value of min_stack.top() into the min_stack. Stack removal rule: Popup data from min_stack and data_stack as the return result of the function. Min function: return min_stack.top().

The second method uses two stacks, data_stack and min_stack. The top of min_stack is the minimum value corresponding to the current data stack. Pushing rule: For data value to be pushed, the number is first pushed onto data_stack. If value<=min_stack.top(), push the number into the min_stack. Rule for ejecting data: If the number at the top of the stack is less than or equal to the number at the top of the min_stack, a data is ejected from the min_stack. Pop data from the data_stack as the return result of the function. Min function: return min_stack.top().

code

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

/ * * *@param {number} x
 * @return {void}* /
MinStack.prototype.push = function(x) {
    if(!this.stack.length) this.minval = x;
    this.stack.push(x)
    if(x<this.minval) this.minval=x;
    this.minst.push(this.minval)
};

/ * * *@return {void}* /
MinStack.prototype.pop = function() {
    this.stack.pop();
    this.minst.pop();
    const length = this.minst.length;
    if (length) {
        this.minval=this.minst[length-1]; }};/ * * *@return {number}* /
MinStack.prototype.top = function() {
    const length = this.stack.length;
    if (length) {
        return this.stack[length - 1];
    } else {
        return null; }};/ * * *@return {number}* /
MinStack.prototype.min = function() {
    const length = this.minst.length;
    if (length) {
        return this.minst[length - 1];
    } else {
        return null; }};/** * 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