本文首發(fā)于我的個(gè)人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/03/target-offer-min-stack.html 作者: Suixin
題目描述
定義棧的數(shù)據(jù)結(jié)構(gòu)行楞，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧中所含最小元素的min函數(shù)（時(shí)間復(fù)雜度應(yīng)為O（1））嗓蘑。
解題思路
使用一個(gè)輔助棧笙以，用來(lái)存儲(chǔ)當(dāng)前棧中的最小值，輔助棧中元素?cái)?shù)量和原始棧一樣多姓建。每次入棧時(shí)，將入棧元素與輔助棧頂元素相比較，如果該元素較小穷吮，則將該元素也入輔助棧严蓖，否則將輔助棧頂元素再入輔助棧一次薄嫡。出棧時(shí)，輔助棧也要出棧颗胡。即保持輔助棧頂元素為當(dāng)前棧的最小元素值毫深。
代碼
Python(2.7.3)
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack = []
self.assist_stack = []
def is_empty(self):
return self.stack == []
def push(self, node):
# write code here
self.stack.append(node)
if not self.assist_stack or node <= self.assist_stack[-1]:
self.assist_stack.append(node)
else:
self.assist_stack.append(self.min())
def pop(self):
# write code here
if self.is_empty():
return
self.assist_stack.pop()
return self.stack.pop()
def top(self):
# write code here
if self.is_empty():
return
return self.stack[-1]
def min(self):
# write code here
while self.assist_stack != []:
return self.assist_stack[-1]
運(yùn)行時(shí)間：24ms
占用內(nèi)存：5860k
參考
https://www.nowcoder.com/profile/589201/codeBookDetail?submissionId=558366
