剑指offer - 包含min函数的栈 - JavaScript
剑指offer - 包含min函数的栈 - JavaScript
心谭博客
发布于 2020-04-21 15:27:10
发布于 2020-04-21 15:27:10
题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数（时间复杂度应为 O（1））。
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数（时间复杂度应为 O（1））。
解法 1: 暴力法
直接遍历栈得到最小的元素，但理论上 min 函数的时间复杂度是 O(N)，不符合题目要求，但可以 ac。
代码如下：
// ac地址：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
// 原文地址：https://xxoo521.com/2020-01-31-stack-min/
/**
* initialize your data structure here.
*/
var MinStack = function() {
this.stack = [];
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.stack.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
const length = this.stack.length;
if (length) {
return this.stack[length - 1];
} else {
return null;
}
};
/**
* @return {number}
*/
MinStack.prototype.min = function() {
const length = this.stack.length;
if (!length) return null;
return Math.min(...this.stack);
};解法 2: 辅助栈
正确的做法是借助一个辅助栈。他们之间有一种对应关系：辅助栈的栈顶元素，就是原栈所有元素的最小值。
对原栈和辅助栈的处理过程如下：
- 元素压入原栈的时候，如果辅助栈为空，或者
元素 <= 辅助栈的栈顶元素，那么将元素也压入辅助栈 - 元素弹出原栈的时候，如果元素等于辅助栈的栈顶元素，辅助栈也弹出元素
这里的判断条件是元素 <= 辅助栈的栈顶元素而不是元素 < 辅助栈的栈顶元素，是为了应对重复元素。例如将 1、2、3、1 依次入栈，采用错误的判断条件，那么辅助栈里面只有 1。在原栈弹出 1 之后，辅助栈为空，就没法获得原栈元素的最小值。
// ac地址：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
// 原文地址：https://xxoo521.com/2020-01-31-stack-min/
/**
* initialize your data structure here.
*/
var MinStack = function() {
this.dataStack = [];
this.minStack = []; // 辅助栈
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.dataStack.push(x);
const length = this.minStack.length;
if (!length) {
this.minStack.push(x);
} else if (x <= this.minStack[length - 1]) {
this.minStack.push(x);
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
const { minStack, dataStack } = this;
if (minStack[minStack.length - 1] === dataStack[dataStack.length - 1]) {
minStack.pop();
}
dataStack.pop();
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
const length = this.dataStack.length;
if (length) {
return this.dataStack[length - 1];
} else {
return null;
}
};
/**
* @return {number}
*/
MinStack.prototype.min = function() {
const length = this.minStack.length;
if (!length) return null;
return this.minStack[length - 1];
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-01-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录