本文由 简悦 SimpRead 转码， 原文地址 https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653190073&idx=1&sn=c20c002127e2ce3fe0c71a00aee70806&chksm=8c990563bbee8c75521c54ea8eb44b009ad07266b1e5fbf22926baf9a7b7302c7e4f7657dbb8&scene=21#wechat_redirect
小灰回忆起当时的情景……
题目：实现一个栈，带有出栈（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）。
喜欢本文的朋友们，欢迎长按下图关注订阅号梦见，收看更多精彩内容
