- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
辅助栈
- stack 支持常规的 push、pop、top 操作。
- 定义一个辅助栈 resStack ，将最小值一直保持在栈顶，来支持常数时间复杂度获取。
constMinStack=function(){this.stack=[];this.resStack=[Infinity];};MinStack.prototype.push=function(x){this.stack.push(x);this.resStack.push(Math.min(this.resStack[this.resStack.length-1],x));};MinStack.prototype.pop=function(){this.stack.pop();this.resStack.pop();};MinStack.prototype.top=function(){returnthis.stack[this.stack.length-1];};MinStack.prototype.getMin=function(){returnthis.resStack[this.resStack.length-1];};
- 时间复杂度: O(1)
- 空间复杂度: O(n)