LeetCode - 155. Min Stack

Thoughts:

it’s because every operation need to be O(1).

Set a stack for normal operation,

and set a minStack for finding the minimum value

Thoughts visuzlization:

MinStack(): initialize stack and minStack

push(): push value to stack and minStack
        * if the value is smaller than minStack's top
          push it to minStack
          else push minStack's top to minStack
          for keeping tracking the minimum value
        ex.
          stack = [0], minStack = [0]
          stack = [0,1], minStack = [0,0]
          stack = [0,1,2], minStack = [0,0,0]
          stack = [0,1,2,-1], minStack = [0,0,0,-1]

pop(): pop value from stack and minStack

top(): return stack's top value

getMin(): return minStack's top value

Code:

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

/**
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
  this.stack.push(val);
  this.minStack.push(
    Math.min(
      val,
      this.minStack.length === 0
        ? val
        : this.minStack[this.minStack.length - 1],
    ),
  );
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  this.stack.pop();
  this.minStack.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];
};

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

Reference

Original link

Stack data structure intro