zui-xiao-zhan.md

最小栈

• 思想

  两个栈，一个原栈，一个备胎栈，前者保存元素，后者保存下标

• 步骤

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对应元素即可。

• 示意图

1. step 1:

2. step 2:

3. step 3:

4. step 4:

5. step 5: