這篇文章給大家分享的是有關(guān)LeetCode如何實現(xiàn)包含min函數(shù)的棧的內(nèi)容。小編覺得挺實用的,因此分享給大家做個參考,一起跟隨小編過來看看吧。
創(chuàng)新互聯(lián)專注于點軍網(wǎng)站建設(shè)服務(wù)及定制,我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供點軍營銷型網(wǎng)站建設(shè),點軍網(wǎng)站制作、點軍網(wǎng)頁設(shè)計、點軍網(wǎng)站官網(wǎng)定制、微信平臺小程序開發(fā)服務(wù),打造點軍網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供點軍網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。
定義棧的數(shù)據(jù)結(jié)構(gòu),請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中,調(diào)用 min、push 及 pop 的時間復(fù)雜度都是 O(1)。
各函數(shù)的調(diào)用總次數(shù)不超過 20000 次
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
O(1)
O(N)
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
# 一個普通棧和一個單調(diào)遞減棧
self.minstack = []
self.stack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.minstack or x <= self.minstack[-1]:
# 如果單調(diào)棧頂為空或者當(dāng)前新值小于等于單調(diào)棧頂才push
# 注意這里等于也需要push. 如果對于重復(fù)的最小值 x 不 push, 那么在后續(xù)的 pop 其中一個 x 之后, 棧頂(不再是 x)就和實際最小值(仍為 x)不一致了
self.minstack.append(x)
def pop(self) -> None:
if not self.stack:
return
x = self.stack.pop()
if x == self.minstack[-1]:
# 如果單調(diào)棧頂恰好等于pop的值, 也要pop單調(diào)棧
self.minstack.pop()
def top(self) -> int:
if not self.stack:
return -1
return self.stack[-1]
def min(self) -> int:
if not self.minstack:
return -1
return self.minstack[-1]
感謝各位的閱讀!關(guān)于“LeetCode如何實現(xiàn)包含min函數(shù)的?!边@篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,讓大家可以學(xué)到更多知識,如果覺得文章不錯,可以把它分享出去讓更多的人看到吧!
分享文章:LeetCode如何實現(xiàn)包含min函數(shù)的棧
分享網(wǎng)址:http://bm7419.com/article32/pcgdpc.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供微信公眾號、云服務(wù)器、網(wǎng)站策劃、營銷型網(wǎng)站建設(shè)、軟件開發(fā)、網(wǎng)站導(dǎo)航
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)