【程序员面试金典】【栈】面试题 03.02 - 栈的最小值
一 目录
不折腾的前端，和咸鱼有什么区别
| 目录 |
|---|
| 一 目录 |
| 二 题目 |
| 三 解题思路 |
| 四 统计分析 |
| 五 解题套路 |
二 题目
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
示例：
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）
链接：https://leetcode-cn.com/problems/min-stack-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* initialize your data structure here.
*/
var MinStack = function() {
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/
根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。
三 解题思路
设计题，直接上代码：
var MinStack = function() {
this.stack = [];
this.sortStack = [];
this.length = 0;
};
MinStack.prototype.push = function(x) {
const length = this.length;
this.stack[length] = x;
// 通过辅助栈，记录每次添加的时候，要如何判断最小值
// sortStack 最末尾一项为添加之前的最小的值
if (!length || this.sortStack[length - 1] > x) {
this.sortStack[length] = x;
} else {
this.sortStack[length] = this.sortStack[length - 1];
}
this.length = length + 1;
};
MinStack.prototype.pop = function() {
const length = this.length;
this.length = length - 1;
return this.stack[length - 1];
};
MinStack.prototype.top = function() {
return this.stack[this.length - 1];
};
MinStack.prototype.getMin = function() {
return this.sortStack[this.length - 1];
};
四 统计分析
本题不需要统计分析。
五 套路分析
本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。
如果小伙伴有更好的思路想法，或者没看懂其中某种解法，欢迎评论留言或者私聊 jsliang~
不折腾的前端，和咸鱼有什么区别！
jsliang 会每天更新一道 LeetCode 题解，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构。
浪子神剑 会每天更新面试题，以面试题为驱动来带动大家学习，坚持每天学习与思考，每天进步一点！
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。