写点什么

LeetCode 题解:155. 最小栈,使用两个栈,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 08 月 28 日
LeetCode题解:155.最小栈,使用两个栈,详细注释

阅读更多系列文章请访问我的GitHub 博客


原题链接:https://leetcode-cn.com/problems/min-stack/


解题思路:


本题解参考了官方题解


  1. 使用两个栈,一个栈保存当前存入的结果,辅助栈保存每次入栈时,当前保存的最小值。

  2. 可以理解为辅助栈中保存了每次入栈操作时,当前的最小值。


复杂度分析:


时间复杂度:各操作均为 O(1)

空间复杂度:O(n)


/**
* initialize your data structure here.
*/
var MinStack = function () {
this.stack = [];
this.minStack = [Infinity]; // 使用无穷大,保证第一个值入栈时,一定会被存入辅助栈
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {
this.stack.push(x);
// 每次存入一个值时,都将当前最小值与存入的值进行比较,保存较小的值。
// 可以理解为,缓存了每次入栈操作时,当前栈的最小值。
this.minStack.push(Math.min(this.minStack[this.minStack.length - 1], x));
};
/**
* @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];
};
复制代码


发布于: 2020 年 08 月 28 日阅读数: 53
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:155.最小栈,使用两个栈,详细注释