python实现时间o(1)的最小栈的实例代码

yipeiwu_com5年前Python基础

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

Python 高级专用类方法的实例详解

Python 高级专用类方法的实例详解 除了 __getitem__ 和 __setitem__ 之外 Python 还有更多的专用函数。某些可以让你模拟出你甚至可能不知道的功能。下面的...

Django框架创建mysql连接与使用示例

本文实例讲述了Django框架创建mysql连接与使用。分享给大家供大家参考,具体如下: 对于Django新手,你刚开始可以不使用MySQL数据库,但一定要学会如何配置使用MySQL。D...

Python下线程之间的共享和释放示例

最近被多线程给坑了下,没意识到类变量在多线程下是共享的,还有一个就是没意识到 内存释放问题,导致越累越大 1.python 类变量 在多线程情况 下的 是共享的 2.python 类变量...

python实现名片管理系统项目

python实现名片管理系统项目

名片管理系统,供大家参考,具体内容如下 环境要求:linux系统、python2.x或python3.x 资源地址:GitHub地址 写在前面的话:笔者之前在初学C/C++时,都曾写过类...

使用NumPy读取MNIST数据的实现代码示例

使用NumPy读取MNIST数据的实现代码示例

NumPy 什么是NumPy NumPy是 Python 语言的一个扩展程序库,支持大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库。主页为https://numpy.o...