LeetCode 题解:155. 最小栈,单个栈存储入栈元素与最小值之差,JavaScript,详细注释
原题链接:https://leetcode-cn.com/problems/min-stack/
解题思路:
参考了详细通俗的思路分析,多解法中的第3个题解。
每次入栈时,stack中保存的都是入栈元素与最小值之差,当入栈的值小于已存储的最小值时,需要更新一次最小值。
第一次入栈时,由于当前没有最小值,需要将入栈的值先设置为最小值,再存储入栈的值与最小值之差,避免查看第一个元素时出错。
pop时,如果pop的值小于0,表示此次入账时,最小值大于入栈的值,且栈顶元素为两者之差。因此出栈后,要更新最小值。
top时:
- 如果top小于0,表示此次入账时,最小值大于入栈的值。因此栈顶存储的是两者之差,入栈元素为最小值,因此直接返回最小值。
- 如果top大于等于0,表示此次入账时,最小值小于入栈的值。栈顶存储的是两者之差,但由于入栈的值更大,因此返回栈顶元素与最小值之和。
getMin时,直接返回当前保存的最小值即可。
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/a01837c0b2a8cc4c72f6e6c14】。文章转载请联系作者。
评论