时间:2021-05-22
这是毕业校招二面时遇到的手写编程题,当时刚刚开始学习python,整个栈写下来也是费了不少时间。毕竟语言只是工具,只要想清楚实现,使用任何语言都能快速的写出来。
何为最小栈?栈最基础的操作是压栈(push)和退栈(pop),现在需要增加一个返回栈内最小值的函数(get_min),要求get_min函数的时间复杂度为o(1)。python的栈肯定是使用list实现,只要将list的append和pop封装到stack类中,即实现了压栈和退栈。如果不考虑时间复杂度,我们第一反应一定是min(),min()可以在不开辟新空间的情况下o(n)的返回栈内最小值。但是如果栈内元素很多,并且get_min方法需要频繁调用时,min高耗时的缺点就被放大,那么理想的方法就是空间换时间来降低时间复杂度。
我们的栈内存在stack_list和min_list,min_list负责存储栈内元素中最小值组成的栈,当新压栈的元素小于等于栈内最小的元素时,将新元素压入min_list。如果退栈的元素等于栈内最小的元素,那么也要将min_list退栈。举例子,我们依次压栈3,2,4,1
初始化
stack_list = [] min_list = []3压栈
stack_list = [3]min_list = [3]2压栈
stack_list = [3, 2]min_list = [3, 2]4压栈
stack_list = [3, 2, 4]min_list = [3, 2]1压栈
stack_list = [3, 2, 4, 1]min_list = [3, 2, 1]get_min只需要返回min_list中最后一个元素,以下是python代码的完整实现
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
最小栈最小栈,能在O(1)内找到栈内序列的最小值,因此此特性经常用于提升算法性能。下面看看它的一种实现。分析过程入栈分析:推入元素到mainstack,只有当当
本文实例讲述了Python栈的实现方法。分享给大家供大家参考,具体如下:Python实现栈栈的数组实现:利用python列表方法代码如下:#列表实现栈,利用py
本文实例讲述了Python实现的括号匹配判断功能。分享给大家供大家参考,具体如下:1.用一个栈【python中可以用List】就可以解决,时间和空间复杂度都是O
本文实例为大家分享了python封装对象实现时间效果的具体代码,供大家参考,具体内容如下#钟表importtimeclassClock():def__init_
本文实例讲述了Python实现的直接插入排序算法。分享给大家供大家参考,具体如下:#-*-coding:utf-8-*-'''直接插入的python实现时间复杂