快捷導(dǎo)航

python實(shí)現(xiàn)時(shí)間o(1)的最小棧的實(shí)例代碼

更新時(shí)間：2018年07月23日 09:41:18 作者：熔遁丶螺旋手里劍

這篇文章主要介紹了python實(shí)現(xiàn)時(shí)間o(1)的最小棧的實(shí)例代碼，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

這是畢業(yè)校招二面時(shí)遇到的手寫(xiě)編程題，當(dāng)時(shí)剛剛開(kāi)始學(xué)習(xí)python，整個(gè)棧寫(xiě)下來(lái)也是費(fèi)了不少時(shí)間。畢竟語(yǔ)言只是工具，只要想清楚實(shí)現(xiàn)，使用任何語(yǔ)言都能快速的寫(xiě)出來(lái)。

何為最小棧？棧最基礎(chǔ)的操作是壓棧(push)和退棧(pop)，現(xiàn)在需要增加一個(gè)返回棧內(nèi)最小值的函數(shù)(get_min)，要求get_min函數(shù)的時(shí)間復(fù)雜度為o(1)。python的?？隙ㄊ鞘褂胠ist實(shí)現(xiàn)，只要將list的append和pop封裝到stack類中，即實(shí)現(xiàn)了壓棧和退棧。如果不考慮時(shí)間復(fù)雜度，我們第一反應(yīng)一定是min()，min()可以在不開(kāi)辟新空間的情況下o(n)的返回棧內(nèi)最小值。但是如果棧內(nèi)元素很多，并且get_min方法需要頻繁調(diào)用時(shí)，min高耗時(shí)的缺點(diǎn)就被放大，那么理想的方法就是空間換時(shí)間來(lái)降低時(shí)間復(fù)雜度。

我們的棧內(nèi)存在stack_list和min_list，min_list負(fù)責(zé)存儲(chǔ)棧內(nèi)元素中最小值組成的棧，當(dāng)新壓棧的元素小于等于棧內(nèi)最小的元素時(shí)，將新元素壓入min_list。如果退棧的元素等于棧內(nèi)最小的元素，那么也要將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中最后一個(gè)元素，以下是python代碼的完整實(shí)現(xiàn)

#!/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

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: