这是毕业校招二面时遇到的手写编程题,当时刚刚开始学习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
初始化
1
2
|
stack_list = []
min_list = []
|
3压栈
1
2
|
stack_list = [ 3 ]
min_list = [ 3 ]
|
2压栈
1
2
|
stack_list = [ 3 , 2 ]
min_list = [ 3 , 2 ]
|
4压栈
1
2
|
stack_list = [ 3 , 2 , 4 ]
min_list = [ 3 , 2 ]
|
1压栈
1
2
|
stack_list = [ 3 , 2 , 4 , 1 ]
min_list = [ 3 , 2 , 1 ]
|
get_min只需要返回min_list中最后一个元素,以下是python代码的完整实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#!/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