[TOC] # 栈简介 栈是一个先入后出的集合 # 问题 **实现一个栈,让这个栈带有出栈(pop),入栈(push),查找最小元素(getMin)这3个方法,并且要保证这3个方法的时间复杂度都是0(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）三个方法。要保证这三个方法的时间复杂度都尽可能小。