写点什么

LeetCode 题解:155. 最小栈,单个栈存储入栈元素与最小值之差,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 09 月 01 日
LeetCode题解:155. 最小栈,单个栈存储入栈元素与最小值之差,JavaScript,详细注释

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



解题思路:



参考了详细通俗的思路分析,多解法中的第3个题解。



  1. 每次入栈时,stack中保存的都是入栈元素与最小值之差,当入栈的值小于已存储的最小值时,需要更新一次最小值。

  2. 第一次入栈时,由于当前没有最小值,需要将入栈的值先设置为最小值,再存储入栈的值与最小值之差,避免查看第一个元素时出错。

  3. pop时,如果pop的值小于0,表示此次入账时,最小值大于入栈的值,且栈顶元素为两者之差。因此出栈后,要更新最小值。

  4. top时:

- 如果top小于0,表示此次入账时,最小值大于入栈的值。因此栈顶存储的是两者之差,入栈元素为最小值,因此直接返回最小值。

- 如果top大于等于0,表示此次入账时,最小值小于入栈的值。栈顶存储的是两者之差,但由于入栈的值更大,因此返回栈顶元素与最小值之和。

  1. getMin时,直接返回当前保存的最小值即可。



/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function (x) {
// 当栈为空时,需要先设置最小值,否则top时会出错
if (!this.stack.length) {
this.min = x;
// 实际入栈的元素始终是当前入栈的值与最小值之差。
this.stack.push(x - this.min);
} else {
// 实际入栈的元素始终是当前入栈的值与最小值之差。
this.stack.push(x - this.min);
// 当入栈的值小于最小值时,需要更新最小值
if (x < this.min) {
this.min = x;
}
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function () {
const pop = this.stack.pop();
// 当出栈的值小于0,表示此次入账时,最小值大于入栈的值,且栈顶元素为两者之差。
// 因此出栈后,要更新最小值。
if (pop < 0) {
this.min = this.min - pop;
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function () {
const top = this.stack[this.stack.length - 1];
// 如果top小于0,表示此次入账时,最小值大于入栈的值。
// 因此栈顶存储的是两者之差,入栈元素为最小值,因此直接返回最小值。
if (top < 0) {
return this.min;
} else {
// 如果top大于等于0,表示此次入账时,最小值小于入栈的值。
// 栈顶存储的是两者之差,但由于入栈的值更大,因此返回栈顶元素与最小值之和。
return top + this.min;
}
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function () {
// 当前保存的最小值,始终是最小值。
return this.min;
};



发布于: 2020 年 09 月 01 日阅读数: 46
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:155. 最小栈,单个栈存储入栈元素与最小值之差,JavaScript,详细注释