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í)遇到的手寫編程題，當(dāng)時(shí)剛剛開(kāi)始學(xué)習(xí)python，整個(gè)棧寫下來(lái)也是費(fèi)了不少時(shí)間。畢竟語(yǔ)言只是工具，只要想清楚實(shí)現(xiàn)，使用任何語(yǔ)言都能快速的寫出來(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í)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

相關(guān)文章

Python Excel實(shí)現(xiàn)自動(dòng)添加編號(hào)
這篇文章主要為大家詳細(xì)介紹了如何使用Python在Excel中實(shí)現(xiàn)自動(dòng)添加編號(hào)效果,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
2025-03-03
使用Python計(jì)算兩個(gè)不同列表的相似度
這篇文章主要介紹了使用Python計(jì)算兩個(gè)不同列表的相似度,Python數(shù)據(jù)開(kāi)發(fā)工作中的需求兩個(gè)不同列表給出相似度，本文實(shí)現(xiàn)判斷數(shù)字類型相似度和字符串類型相似度，非常實(shí)用,需要的朋友可以參考下
2023-07-07
Python網(wǎng)絡(luò)編程基于多線程實(shí)現(xiàn)多用戶全雙工聊天功能示例
這篇文章主要介紹了Python網(wǎng)絡(luò)編程基于多線程實(shí)現(xiàn)多用戶全雙工聊天功能,結(jié)合實(shí)例形式分析了Python網(wǎng)絡(luò)編程中使用多線程進(jìn)行多用戶異步通信的原理與相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下
2018-04-04
OpenCV黑帽運(yùn)算(BLACKHAT)的使用
本文主要介紹了OpenCV黑帽運(yùn)算(BLACKHAT)的使用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2022-08-08
Python遍歷文件夾和讀寫文件的實(shí)現(xiàn)代碼
這篇文章主要介紹了Python遍歷文件夾和讀寫文件的實(shí)現(xiàn)代碼,需要的朋友可以參考下
2016-08-08
python機(jī)器學(xué)習(xí)創(chuàng)建基于規(guī)則聊天機(jī)器人過(guò)程示例詳解
這篇文章主要為大家介紹了python實(shí)現(xiàn)基于規(guī)則聊天機(jī)器人的過(guò)程示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪
2021-11-11
Python利用Selenium實(shí)現(xiàn)自動(dòng)觀看學(xué)習(xí)通視頻
Selenium是一個(gè)用于Web應(yīng)用程序測(cè)試的工具。Selenium測(cè)試直接運(yùn)行在瀏覽器中，就像真正的用戶在操作一樣。本文主要介紹了利用Selenium實(shí)現(xiàn)自動(dòng)觀看學(xué)習(xí)通視頻，需要的同學(xué)可以參考一下
2021-12-12
關(guān)于Python排序問(wèn)題(冒泡/選擇/插入)
這篇文章主要介紹了關(guān)于Python排序問(wèn)題(冒泡/選擇/插入),學(xué)過(guò)C語(yǔ)言肯定接觸過(guò)排序問(wèn)題，我們最常用的也就是冒泡排序、選擇排序、插入排序,需要的朋友可以參考下
2023-04-04
python 基于空間相似度的K-means軌跡聚類的實(shí)現(xiàn)
這篇文章主要介紹了python 基于空間相似度的K-means軌跡聚類的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2021-03-03
使用PyTorch實(shí)現(xiàn)MNIST手寫體識(shí)別代碼
今天小編就為大家分享一篇使用PyTorch實(shí)現(xiàn)MNIST手寫體識(shí)別代碼，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2020-01-01