这是毕业校招二面时遇到的手写编程题,当时刚刚开始学习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

 

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

python实现快速排序详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。