每日算法：最小栈（包含getMin函数的栈）
回复交流，加入前端编程面试算法每日一题群
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x)—— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin()—— 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解答在常数时间内检索到最小元素的栈，即仅需保证 getMin 的时间复杂度为 O(1) 即可
class MinStack {
constructor () {
this.length = 0;
this.content = [];
this.mins = [];
}
push (val) {
const curMin = this.mins[this.length - 1] !== undefined ? this.mins[this.length - 1] : Infinity;
this.content[this.length++] = val;
this.mins[this.length - 1] = Math.min(curMin, val);
}
pop () {
return this.content[--this.length]
}
top () {
return this.content[this.length - 1]
}
getMin () {
return this.mins[this.length - 1];
}
}
时间复杂度：进栈O(1)，出栈O(n)，获取栈顶元素O(1)，获取最小元素O(1)
空间复杂度：O(n)
最后
号内回复：
120 套模版评论