python实现时间o(1)的最小栈详解编程语言
这是毕业校招二面时遇到的手写编程题,当时刚刚开始学习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
原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/12487.html
cjavapython相关文章
- Python常用代码_python画图代码大全
- python实现矩阵的转置_Python实现矩阵转置的方法分析
- python socket recvfrom_Python:socket.recvfrom()不返回任何地址
- Python:利用python代码编程实现将视频的avi格式转换为MP4格式
- python制作自动交易程序_Python如何实现自动化交易
- python猴子摘桃问题_python解决简单实际问题
- python多线程有几种实现方法详解编程语言
- Python 实现的”冒泡排序”详解编程语言
- 用Python实现二分查找详解编程语言
- python在windows下操作word的方法详解编程语言
- python collection模块中几种数据结构(Counter、OrderedDict、namedtup)详解编程语言
- python多线程不断刷新网页的代码详解编程语言
- Python实现HTTP代理服务器详解编程语言
- Python开发系列课程(12) – 图形用户界面和游戏开发详解编程语言
- python实现快速排序详解编程语言
- Python数据清洗基本流程详解编程语言
- python做一个http接口测试框架详解编程语言
- Python 基于python实现的http+json协议接口自动化测试框架源码(实用改进版)详解编程语言
- python事件驱动的小例子详解编程语言
- python单线程下实现多个socket并发详解编程语言
- python之ftp作业【还未完成】详解编程语言
- 四款后起编程语言能否成功挑战Python的王者地位
- Python实现MySQL数据库的读取(python读取mysql)