溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這是畢業校招二面時遇到的手寫編程題，當時剛剛開始學習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
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
