python实现时间o(1)的最小栈的实例代码
作者:熔遁丶螺旋手里剑 时间:2021-08-01 15:24:42
这是毕业校招二面时遇到的手写编程题,当时刚刚开始学习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代码的完整实现
#!/usr/bin/python
# -*- coding: utf-8 -*-
class stack(object):
stack_list = []
min_list = []
min = None
def push(self, x):
if not self.stack_list:
self.min = x
self.min_list.append(self.min)
self.stack_list.append(x)
return
self.stack_list.append(x)
if self.min >= x:
self.min = x
self.min_list.append(self.min)
return
def pop(self):
pop_result = None
if self.stack_list:
pop_result = self.stack_list[-1]
if self.stack_list.pop() == self.min:
self.min_list.pop()
if self.min_list:
self.min = self.min_list[-1]
else:
self.min = None
return pop_result
else:
self.min = None
return pop_result
def print_stack(self):
print "stack---->", self.stack_list
return
def get_min(self):
return self.min
来源:https://www.cnblogs.com/baiyb/p/8443337.html
标签:python,时间o(1),最小栈
0
投稿
猜你喜欢
1 行 Python 代码快速实现 FTP 服务器
2022-02-19 18:17:41
ASP批量生成静态页面的写法(批量生成技巧iframe)
2011-02-24 11:01:00
Python性能分析工具pyinstrument提高代码效率
2021-01-24 02:37:44
作为Web开发人员,我为什么喜欢Google Chrome浏览器
2011-08-29 15:37:47
PHP实现表单处理方法详解
2023-05-25 07:39:18
python 实现目录复制的三种小结
2023-09-01 12:17:20
Elasticsearch属性单词常用解析说明
2023-06-12 14:47:36
python将ansible配置转为json格式实例代码
2023-11-03 02:32:51
窥探jQuery——面向JavaScript程序员
2008-06-17 14:35:00
解决tensorflow/keras时出现数组维度不匹配问题
2023-01-01 04:16:24
python 如何对Series中的每一个数据做运算
2023-11-19 23:33:07
python中模块的__all__属性详解
2022-10-16 08:59:18
Python修改Excel数据的实例代码
2021-05-24 12:40:29
ORACLE数据库查看执行计划的方法
2012-06-06 20:15:52
在ASP中使用SQL语句之6:存储过程查询
2007-08-11 12:44:00
从数据表中取出第n条到第m条的记录的方法
2009-02-19 13:40:00
pyqt5 使用label控件实时显示时间的实例
2021-01-29 14:54:17
python -v 报错问题的解决方法
2022-04-03 03:07:29
分享一枚pycharm激活码适用所有pycharm版本我的pycharm2020.2.3激活成功
2023-10-07 19:07:43
Jupyter加载文件的实现方法
2021-11-12 23:16:15