Leetcode 155 Min Stack
Min Stack – LeetCode
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
For Javascript users, we can utilized an array to implement most of the functionalities in O(1) time since both push and pop from array are constant time operations.
But for getMin we need to keep another stack called minStack to store it. The top of the minStack represents the minimum value of the stack. The way we update the minStack is as follow:
- When pushing a new value into the stack, we check if the value is smaller than the current top of the
minStack, if yes we push the value tominStackas well, otherwise we push the current top of theminStacktominStackagain.
Solution
var MinStack = function() {
this.stack = [];
this.minStack = [ Infinity ]
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
this.stack.push(val);
this.minStack.push(Math.min(val, this.getMin()))
};
/**
* @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()
*/