155. Min Stack

Difficulty:
Related Topics:
Similar Questions:

Problem

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.

pop() -- Removes the element on top of the stack.

top() -- Get the top element.

getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Solution 1

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

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
  if (this.min.length === 0 || x <= this.min[this.min.length - 1]) this.min.push(x);
  this.stack.push(x);
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  var val = this.stack.pop();
  if (val === this.min[this.min.length - 1]) this.min.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this.stack.length ? this.stack[this.stack.length - 1] : 0;
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  return this.min.length ? this.min[this.min.length - 1] : 0;
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = Object.create(MinStack).createNew()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

Explain:

两个栈,一个存值,一个存最小值。

Complexity:

Solution 2

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

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

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  if (!this.length) return;
  var val = this.stack.pop();
  if (val === this.min) {
    this.min = this.stack.pop();
  }
  this.length--;
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this.length ? this.stack[this.stack.length - 1] : 0;
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  return this.min;
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = Object.create(MinStack).createNew()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

Explain:

一个栈,同时存值和最小值。

Complexity:

Solution 3

/**
 * initialize your data structure here.
 */
var MinStack = function() {
  this.Node = function (val) {
    this.val = val;
    this.min = 0;
    this.next = null;
  };
  this.head = null;
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
  var node = new this.Node(x);
  if (this.head) {
    node.next = this.head;
    node.min = Math.min(x, this.head.min);
  } else {
    node.min = x;
  }
  this.head = node;
};

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

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this.head ? this.head.val : 0;
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  return this.head ? this.head.min : 0;
};

/** 
 * Your MinStack object will be instantiated and called as such:
 * var obj = Object.create(MinStack).createNew()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

Explain:

用链表模拟栈,每个节点存储值 val,最小值 min,下一个节点 next

Complexity: