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







以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持中文源码网。