字节&leetcode155：最小栈（包含getMin函数的栈）

[sisterAn]

设计一个支持 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.

附leetcode地址：leetcode

[chenzesam]

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];
 }
}

[13001920223]

var MinStack = function() {
 this.stack = [];
 this.min = Number.MAX_SAFE_INTEGER;
};


MinStack.prototype.push = function(x) {
 if(this.min >= x){
 this.stack.push(x);
 this.min = x;
 } else {
 this.stack.push(x)
 }
};

MinStack.prototype.pop = function() {
 const min = this.stack.pop()
 if(min == this.min){
 this.min = Math.min(...this.stack)
 }
};

MinStack.prototype.top = function() {
 return this.stack[this.stack.length-1];
};

MinStack.prototype.getMin = function() {
 return this.min;
};

[sisterAn]

在常数时间内检索到最小元素的栈，即仅需保证 getMin 的时间复杂度为 O(1) 即可

var MinStack = function() {
 this.items = []
 this.min = null
};

// 进栈
MinStack.prototype.push = function(x) {
 if(!this.items.length) this.min = x 
 this.min = Math.min(x, this.min)
 this.items.push(x) 
};

// 出栈
MinStack.prototype.pop = function() {
 let num = this.items.pop() 
 this.min = Math.min(...this.items)
 return num
};

// 获取栈顶元素
MinStack.prototype.top = function() {
 if(!this.items.length) return null
 return this.items[this.items.length -1] 
};

// 检索栈中的最小元素
MinStack.prototype.getMin = function() {
 return this.min
};

时间复杂度：进栈O(1)，出栈O(n)，获取栈顶元素O(1)，获取最小元素O(1)

空间复杂度：O(n)

leetcode

[XGHeaven]

随便看了下 😂
@chenzesam 你没有考虑 push(0) 的情况。
@sisterAn 出栈也可以做到 O(1) 的，空间复杂度不变，见上面的那个老哥
如果 n 很大而且空间要求很严格的话，可以启用 mins 数组的压缩，不过感觉得不偿失

[chenzesam]

@XGHeaven 可以举个 test case 吗?

[Mr-jili]

@chenzesam pop感觉不好使吧，只是改变length，但数组没有去除

[chenzesam]

@Mr-jili 只是将栈的功能实现了, 不然使用数组的 pop 和 push, 那就不需要实现栈了. length 只是用来划的

[XGHeaven]

@chenzesam 直接实例化之后跑这个

[zhangxiaos]

class MinStack{
 constructor(){
 this.min = undefined // 存放最小值
 this.secondMin = undefined // 存放第二小值
 this.stack = []
 }
 push(item){
 this.stack.push(item)
 if (this.min === undefined){
 this.min = item
 }
 if (item < this.min){
 this.secondMin = this.min
 this.min = item
 }
 }
 pop(){
 const popItem = this.stack.pop()
 if (popItem === this.min){
 this.min = this.secondMin
 }
 return popItem
 }
 top(){
 if (!this.stack.length) return null
 return this.stack[this.stack.length - 1]
 }
 getMin(){
 if (!this.stack.length) return null
 console.log('min:', this.min)
 return this.min
 }
 }

 const minStack = new MinStack();
 minStack.push(-2);
 minStack.push(0);
 minStack.push(-3);
 minStack.getMin(); // --> 返回 -3.
 minStack.pop();
 minStack.top(); // --> 返回 0.
 minStack.getMin(); // --> 返回 -2.

[zero9527]

@chenzesam 直接实例化之后跑这个

push 没有return 一个返回值，就相当于return undefined啊

[zhangxuyang950313]

function MinStack() {
 let list = [];
 let min = null;
 this.push = val => {
 if (typeof val === 'number' && !Number.isNaN(val)) {
 list.push(val);
 min = min === null ? val : Math.min(min, val);
 } else if (Array.isArray(val)) {
 list.push(...val);
 min = min === null ? Math.min(...val) : Math.min(...[min, ...val]);
 }
 return list.length;
 };
 this.pop = () => {
 const last = list.pop();
 if (last === min) {
 min = Math.min(...list);
 }
 return last;
 };
 this.top = () => {
 return list[list.length - 1];
 };
 this.getMin = () => {
 return min;
 };
}

[VivenZZ]

关键点应该是常数时间内找到最小值，我就将最小值定义一个变量。
在添加和移除元素的时候 都会重置最小值

function MinStack() {
 let items = []
 let min
 this.push = function(item) {
 min = min && item > min ? min : item
 return items.push(item)
 }
 this.pop = function(){
 let item = items.pop()
 min = item > min ? min : Math.min(...items)
 return item
 }
 this.getMin = function() {
 return min
 }
 this.top = function(){
 return items[items.length - 1 ] 
 }
}