資訊專欄INFORMATION COLUMN
摘要：刪除棧頂?shù)脑亍？梢粤硗庑陆ㄒ粋€(gè)棧來(lái)順序存入數(shù)據(jù)最小值。另外在數(shù)據(jù)入棧時(shí)需要判斷該值是否比輔助棧的棧頂元素的值更小，如果更小，也應(yīng)該將它加入輔助棧。并且需要判斷輔助棧是否為空，在不空的條件下才可以取棧頂元素比較，否則會(huì)溢出。
LeetCode 155：最小棧 Min Stack
設(shè)計(jì)一個(gè)支持 push，pop，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。
push(x) -- 將元素 x 推入棧中。
pop() -- 刪除棧頂?shù)脑亍?/p>
top() -- 獲取棧頂元素。
getMin() -- 檢索棧中的最小元素。
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.解題思路：
起初我以為定義一個(gè)指針指向最小值即可，后面才想到在棧中彈出元素時(shí)，如果彈出的元素是最小值，那這個(gè)指針就需要更 改選擇另一個(gè)最小元素。沒(méi)辦法，想做到入棧出棧和彈出最小值均為 O(1) 的時(shí)間復(fù)雜度，那么只能犧牲空間來(lái)?yè)Q。可以另外新建一個(gè)棧來(lái)順序存入數(shù)據(jù)最小值。
注意：Python中沒(méi)有多帶帶的 Stack 數(shù)據(jù)結(jié)構(gòu)，其實(shí)它的數(shù)組就有彈出和壓入功能。也可以用 collections.deque() 數(shù)據(jù)結(jié)構(gòu)。 另外在數(shù)據(jù)入棧時(shí)需要判斷該值是否比輔助棧的棧頂元素的值更小，如果更小，也應(yīng)該將它加入輔助棧。并且需要判斷輔助棧是否為空，在不空的條件下才可以取棧頂元素比較，否則會(huì)溢出。
事實(shí)上每次都要調(diào)用函數(shù)判斷是否為空這個(gè)操作，相對(duì)這道題的運(yùn)行時(shí)間來(lái)說(shuō)很耗時(shí)，就這道題而言是可以避免的，只需給輔助棧加入整型最大值作為棧底元素即可。
Java：class MinStack {
Stack s1 = new Stack<>();//初始化棧
Stack s2 = new Stack<>();//輔助棧順序存入最小值
public MinStack() {
s2.push(Integer.MAX_VALUE);//先加入整型最大值在棧底，避免判斷輔助棧是否為空
}
public void push(int x) {
s1.push(x);
if (s2.peek() >= x) s2.push(x);//比棧頂元素值小或相等就加入輔助棧
}
public void pop() {
int tmp = s1.pop();
if (tmp == s2.peek()) s2.pop();//彈出棧的元素值如果和輔助棧頂元素值相等，也在輔助棧彈出它
}
public int top() {
return s1.peek();//返回棧頂元素
}
public int getMin() {
return s2.peek();//返回輔助棧棧頂元素即是最小值
}
}
Python3：
class MinStack:
#初始化數(shù)據(jù)結(jié)構(gòu)(數(shù)組)，s2作為輔助棧加入整形最大值做棧底，避免判斷輔助棧是否為空
def __init__(self):
self.s1 = []
self.s2 = []
self.s2.append(sys.maxsize)
def push(self, x: int) -> None:
self.s1.append(x)
#取棧頂元素直接用數(shù)組負(fù)值索引 Array[-1] 取最后一個(gè)值
if self.s2[-1] >= x: self.s2.append(x)
def pop(self) -> None:
tmp = self.s1.pop()
if tmp == self.s2[-1]: self.s2.pop()
def top(self) -> int:
return self.s1[-1]
def getMin(self) -> int:
return self.s2[-1]
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/75733.html
摘要：題目地址題目描述設(shè)計(jì)一個(gè)支持，，操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。將元素推入棧中。刪除棧頂?shù)脑?。示例返回返回返回解答每次入棧都放入兩個(gè)元素，分別是當(dāng)前元素，和當(dāng)前的最小元素因此放入之前需要和當(dāng)前值進(jìn)行比較。 題目地址：https://leetcode-cn.com/probl...題目描述：設(shè)計(jì)一個(gè)支持 push，pop，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。 p...
摘要：雙棧法復(fù)雜度時(shí)間空間思路暴力的方法是遍歷一遍棧得出最小值，這樣不用任何空間。因?yàn)檫@個(gè)最小值的順序也是先進(jìn)后出，我們同樣用一個(gè)棧來(lái)記錄。這樣主棧在時(shí)，如果該值小于等于副棧頂，就也進(jìn)副棧中。當(dāng)主棧時(shí)，如果出的元素是副棧棧頂?shù)脑?，副棧也要? Min Stack Design a stack that supports push, pop, top, and retrieving themin...
摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：如果繼續(xù)降序，說(shuō)明又向左走了，這樣等到下次向右走得時(shí)候也要再次更新最小值。這樣，序列無(wú)效的條件就是違反了這個(gè)最小值的限定。我們同樣可以用本題的方法解，不過(guò)是從數(shù)組的后面向前面遍歷，因?yàn)樵诤竺媪?。棧的增長(zhǎng)方向也是從高向低了。 Verify Preorder Sequence in Binary Search Tree Given an array of numbers, verify ...
閱讀 3268·2023-04-26 01:31
閱讀 1905·2023-04-25 22:08
閱讀 3464·2021-09-01 11:42
閱讀 2837·2019-08-30 12:58
閱讀 2179·2019-08-29 18:31
閱讀 2442·2019-08-29 17:18
閱讀 3074·2019-08-29 13:01
閱讀 2561·2019-08-28 18:22
