题目分析
这个题目考察我们对栈的理解和我们的思维能力,不难想到,希望小伙伴们可以先思考。
栈
我们只能利用两个栈,而且栈只可以取出顶部元素,无法进行排序,因此我们要好好使用它的性质。
因为每次push一个数,而不是将乱序的栈进行排序,这就给我们提供了思路。如果栈是有序的,那么再插入一个元素时有什么变化呢?如栈s是7,5,3,1。这时插入4,我们还想让栈是有序的,那么我们就需要将小于4的元素先存放起来,我们可以先存到另一个栈tmpS中,此时s:7,5,tmpS:1,3。这时我们可以将4加入到s中,再将tmpS中的元素取出放回到s中即可。
算法的**时间复杂度为$O(n^2)$,空间复杂度为$O(n)$**,其中n为元素个数。
1 | #include<iostream> |
优化栈
在上面的方法中,我们每次push都需要将小于val的元素都放入tmpS中,最后将tmpS中的元素再放回到s中。val的值非常大,那么每次都需要将所有元素弹出再插入一次,会浪费非常多的时间。
我们可以不将tmpS栈中的元素都压入s中。就保持s中的元素是大于等于val的,并且s是递减栈,而tmpS中的元素是递增的,且元素值都小于val。这样再插入下一个值k时,如果k >= val,我们就只用将s中小于k,大于等于val的值放入tmpS中即可,因为小于val的值已经放入tmpS中了,同理如果k < val,我们只用将tmpS中大于等于k,小于val的值放入s中即可,因为大于等于val的值已经放入s中了。
我们可以比较一下7,5,3,1插入2,4,6时,两个方法操作push和pop的次数。
方案一:tmpS压入1,s弹出1,s压入2,s压入1,tmpS弹出1。此时2插入完毕,push3次,pop2次。tmpS压入1,s弹出1,tmpS压入2,s弹出2,tmpS压入3,s弹出3,s压入4,s压入3,tmpS弹出3,s压入2,tmpS弹出2,s压入1,tmpS弹出1。此时4插入完毕,push7次,pop6次。tmpS压入1,s弹出1,tmpS压入2,s弹出2,tmpS压入3,s弹出3,tmpS压入4,s弹出4,tmpS压入5,s弹出5,s压入6,s压入5,tmpS弹出5,s压入4,tmpS弹出4,s压入3,tmpS弹出3,s压入2,tmpS弹出2,s压入1,tmpS弹出1。此时6插入完毕,push11次,pop10次。一共三次操作后,push21次,pop18次。
方案二:tmpS压入1,s弹出1,s压入2。此时2插入完毕,push2次,pop1次。tmpS压入3,s弹出3,s压入4。此时4插入完毕,push2次,pop1次。tmpS压入5,s弹出5,s压入6。此时6插入完毕,push2次,pop1次。一共三次操作后,push6次,pop3次。
但是要注意peek操作和pop操作。因为要获取全体元素的最小值,而最小值存放在tmpS栈中,因此要先将tmpS中的元素全部压入s中才能够peek和pop。
最坏情况下算法的**时间复杂度为$O(n^2)$,空间复杂度为$O(n)$**,其中n为元素个数,但是绝大多数情况下都比第一种算法快得多。
1 | #include<iostream> |
刷题总结
有趣的想法,方案二是我在看题解中发现的一种解法,非常非常的牛,因此介绍给小伙伴们学习。