python實現(xiàn)時間o(1)的最小棧的實例代碼
這是畢業(yè)校招二面時遇到的手寫編程題，當(dāng)時剛剛開始學(xué)習(xí)python，整個棧寫下來也是費了不少時間。畢竟語言只是工具，只要想清楚實現(xiàn)，使用任何語言都能快速的寫出來。
何為最小棧？棧最基礎(chǔ)的操作是壓棧(push)和退棧(pop)，現(xiàn)在需要增加一個返回棧內(nèi)最小值的函數(shù)(get_min)，要求get_min函數(shù)的時間復(fù)雜度為o(1)。python的棧肯定是使用list實現(xiàn)，只要將list的append和pop封裝到stack類中，即實現(xiàn)了壓棧和退棧。如果不考慮時間復(fù)雜度，我們第一反應(yīng)一定是min()，min()可以在不開辟新空間的情況下o(n)的返回棧內(nèi)最小值。但是如果棧內(nèi)元素很多，并且get_min方法需要頻繁調(diào)用時，min高耗時的缺點就被放大，那么理想的方法就是空間換時間來降低時間復(fù)雜度。
我們的棧內(nèi)存在stack_list和min_list，min_list負(fù)責(zé)存儲棧內(nèi)元素中最小值組成的棧，當(dāng)新壓棧的元素小于等于棧內(nèi)最小的元素時，將新元素壓入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中最后一個元素，以下是python代碼的完整實現(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
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
- Python基于列表模擬堆棧和隊列功能示例
- Python實現(xiàn)基本數(shù)據(jù)結(jié)構(gòu)中棧的操作示例
- Python數(shù)據(jù)結(jié)構(gòu)之棧、隊列的實現(xiàn)代碼分享
- Python棧算法的實現(xiàn)與簡單應(yīng)用示例
- Python算法應(yīng)用實戰(zhàn)之棧詳解
- Python 數(shù)據(jù)結(jié)構(gòu)之堆棧實例代碼
- 如何用C語言、Python實現(xiàn)棧及典型應(yīng)用
- Python實現(xiàn)包含min函數(shù)的棧
- Python棧類實例分析
- Python實現(xiàn)棧的方法
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了如何使用Python在Excel中實現(xiàn)自動添加編號效果,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2025-03-03
這篇文章主要介紹了使用Python計算兩個不同列表的相似度,Python數(shù)據(jù)開發(fā)工作中的需求兩個不同列表給出相似度，本文實現(xiàn)判斷數(shù)字類型相似度和字符串類型相似度，非常實用,需要的朋友可以參考下2023-07-07
Python網(wǎng)絡(luò)編程基于多線程實現(xiàn)多用戶全雙工聊天功能示例
這篇文章主要介紹了Python網(wǎng)絡(luò)編程基于多線程實現(xiàn)多用戶全雙工聊天功能,結(jié)合實例形式分析了Python網(wǎng)絡(luò)編程中使用多線程進行多用戶異步通信的原理與相關(guān)實現(xiàn)技巧,需要的朋友可以參考下2018-04-04
本文主要介紹了OpenCV黑帽運算(BLACKHAT)的使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
這篇文章主要介紹了Python遍歷文件夾和讀寫文件的實現(xiàn)代碼,需要的朋友可以參考下2016-08-08
python機器學(xué)習(xí)創(chuàng)建基于規(guī)則聊天機器人過程示例詳解
這篇文章主要為大家介紹了python實現(xiàn)基于規(guī)則聊天機器人的過程示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步早日升職加薪2021-11-11
Python利用Selenium實現(xiàn)自動觀看學(xué)習(xí)通視頻
Selenium是一個用于Web應(yīng)用程序測試的工具。Selenium測試直接運行在瀏覽器中，就像真正的用戶在操作一樣。本文主要介紹了利用Selenium實現(xiàn)自動觀看學(xué)習(xí)通視頻，需要的同學(xué)可以參考一下2021-12-12
這篇文章主要介紹了關(guān)于Python排序問題(冒泡/選擇/插入),學(xué)過C語言肯定接觸過排序問題，我們最常用的也就是冒泡排序、選擇排序、插入排序,需要的朋友可以參考下2023-04-04
python 基于空間相似度的K-means軌跡聚類的實現(xiàn)
這篇文章主要介紹了python 基于空間相似度的K-means軌跡聚類的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
今天小編就為大家分享一篇使用PyTorch實現(xiàn)MNIST手寫體識別代碼，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-01-01