漫画算法：最小栈的实现
source link: https://www.cxyxiaowu.com/3937.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
小灰回忆起当时的情景……
题目：实现一个栈，带有出栈（pop），入栈（push），取最小元素（getMin）三个方法。要保证这三个方法的时间复杂度都是O（1）。
小灰的想法：
1.创建一个整型变量 min，初始值-1
2.当第一个元素进栈时，让min=0，即把唯一的元素当做最小值。
3.之后每当一个新元素近栈，让新元素和min指向位置的元素比较大小。如果Stack[min]大于新元素，则min等于新元素的下标；Stack[min]小于新元素，则不做改变。
4.当调用getMin方法的时候，直接返回min所指向位置的元素即可。
按这个思路，近栈、出栈、取最小值的时间复杂度都是O(1)，空间复杂度也是O(1)。
回忆到此结束……
解法：
1.设原有的栈叫做栈A，此时创建一个额外的栈B，用于辅助原栈A。
2.当第一个元素进入栈A的时候，让新元素的下标进入栈B。这个唯一的元素是栈A的当前最小值。（考虑到栈中元素可能不是类对象，所以B栈存储的是A栈元素的下标）
3.每当新元素进入栈A时，比较新元素和栈A当前最小值的大小，如果小于栈A当前最小值，则让新元素的下标进入栈B，此时栈B的栈顶元素就是栈A当前最小值的下标。
4.每当栈A有元素出栈时，如果出栈元素是栈A当前最小值，则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的，是栈A当中原本第二小的元素，代替刚才的出栈元素成为了栈A的当前最小值。（备胎转正）
5.当调用getMin方法的时候，直接返回栈B的栈顶所指向的栈A对应元素即可。
这个解法中近栈、出栈、取最小值的时间复杂度都是O(1)，最坏情况空间复杂度是O(N)。
扩展题目：
实现一个队列，带有出队（deQueue），入队（enQueue），取最小元素（getMin）三个方法。要保证这三个方法的时间复杂度都是O（1）。
喜欢本文的朋友们，欢迎长按下图关注订阅号梦见，收看更多精彩内容
原文始发于微信公众号（程序员小灰）：漫画算法：最小栈的实现
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK