%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%841
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%842
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%843
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%844
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%845
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%847
小灰回忆起当时的情景……
%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%951
%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%952
%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%953
%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%954
%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%955
题目：实现一个栈，带有出栈（pop），入栈（push），取最小元素（getMin）三个方法。要保证这三个方法的时间复杂度都是O（1）。
%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%956
%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%957
小灰的想法：
1.创建一个整型变量 min，初始值-1
2.当第一个元素进栈时，让min=0，即把唯一的元素当做最小值。
3.之后每当一个新元素近栈，让新元素和min指向位置的元素比较大小。如果Stack[min]大于新元素，则min等于新元素的下标；Stack[min]小于新元素，则不做改变。
4.当调用getMin方法的时候，直接返回min所指向位置的元素即可。
%e6%9c%80%e5%b0%8f%e6%a0%88%e7%9a%84%e5%ae%9e%e7%8e%b01
按这个思路，近栈、出栈、取最小值的时间复杂度都是O(1)，空间复杂度也是O(1)。
%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%958
%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%959
%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9510
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%a4%b1%e6%9c%9b
回忆到此结束……
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%848
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%849
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8410
%e6%9c%80%e5%b0%8f%e6%a0%88%e7%9a%84%e5%ae%9e%e7%8e%b02
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8411
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8412
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8413
解法：
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对应元素即可。
%e6%9c%80%e5%b0%8f%e6%a0%88%e7%9a%84%e5%ae%9e%e7%8e%b03
这个解法中近栈、出栈、取最小值的时间复杂度都是O(1)，最坏情况空间复杂度是O(N)。
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8414
扩展题目：
实现一个队列，带有出队（deQueue），入队（enQueue），取最小元素（getMin）三个方法。要保证这三个方法的时间复杂度都尽可能小。
%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%8415
网友评论