第 30 題：定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個能夠得到棧最小元素的 min 函數(shù)
傳送門：AcWing：包含min函數(shù)的棧，?？途W(wǎng) online judge 地址。
設(shè)計(jì)一個支持 push，pop，top 等操作并且可以在 O(1) 時間內(nèi)檢索出最小元素的堆棧。
- push(x)–將元素x插入棧中
- pop()–移除棧頂元素
- top()–得到棧頂元素
- getMin()–得到棧中最小元素
樣例：
MinStack minStack = new MinStack(); minStack.push(-1); minStack.push(3); minStack.push(-4); minStack.getMin(); --> Returns -4. minStack.pop(); minStack.top(); --> Returns 3. minStack.getMin(); --> Returns -1.
思路：
- 定義兩個棧，一個存放入的值，另一個存最小值，兩個棧應(yīng)該是同步 push 和 pop，否則還要分類討論，代碼編寫容易出錯。
- 因?yàn)橐?
實(shí)現(xiàn)當(dāng)前棧中最小，很容易想到用空間換時間，因此可以設(shè)置一個和底層
Stack同步的、稱之為“最小?！钡臈３蓡T。具體操作如下代碼所示。
Python 代碼：
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.helper = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
if len(self.stack) == 0:
self.helper.append(x)
self.stack.append(x)
else:
# 如果將要 push 的元素比輔助棧的棧頂元素還大，不能放這個元素，
# 此時應(yīng)該把輔助棧的棧頂元素再復(fù)制一份
peek = self.helper[-1]
if x > peek:
self.stack.append(x)
self.helper.append(peek)
else:
self.stack.append(x)
self.helper.append(x)
def pop(self):
"""
:rtype: void
"""
if len(self.stack) == 0:
return
# 同步 pop 元素
self.helper.pop()
return self.stack.pop()
def top(self):
"""
:rtype: int
"""
return self.stack[-1]
def getMin(self):
"""
:rtype: int
"""
return self.helper[-1]
Java 代碼：
import java.util.Stack;
public class Solution {
private Stack<Integer> minStack = new Stack<>();
private Stack<Integer> dataStack = new Stack<>();
public void push(int node) {
if (minStack.isEmpty()) {
minStack.push(node);
dataStack.push(node);
return;
}
int curMin = minStack.peek();
if (node < curMin) {
minStack.push(node);
} else {
minStack.push(curMin);
}
dataStack.push(node);
}
public void pop() {
minStack.pop();
dataStack.pop();
}
public int top() {
return dataStack.pop();
}
public int min() {
return minStack.peek();
}
}
思路2：我們除了維護(hù)基本的棧結(jié)構(gòu)之外，還需要維護(hù)一個“輔助?！?。下面介紹如何維護(hù)單調(diào)棧：做到以下兩點(diǎn)，輔助棧的棧頂元素，就是當(dāng)前棧中的最小數(shù)。
1、當(dāng)我們向棧中壓入一個數(shù)時，如果該數(shù)小于（只要小于）“輔助?！钡臈ｍ斣兀瑒t將該數(shù)同時壓入“輔助棧”中；否則，不壓入。由于棧具有先進(jìn)后出性質(zhì)，所以在該數(shù)被彈出之前，“輔助?！敝幸恢贝嬖谝粋€數(shù)比該數(shù)小，所以該數(shù)一定不會被當(dāng)做最小數(shù)輸出。
2、當(dāng)我們從棧中彈出一個數(shù)時，如果該數(shù)等于單調(diào)棧的棧頂元素，同時將單調(diào)棧的棧頂元素彈出。
時間復(fù)雜度：四種操作都只有常數(shù)次入棧出棧操作，所以時間復(fù)雜度都是 。
Python 代碼：
# 定義兩個棧，一個存放入的值，另一個存最小值，兩個棧應(yīng)該是同步 push 和 pop，否則還要分類討論，代碼編寫容易出錯。
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.helper = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
# 無論如何都 push
self.stack.append(x)
# 如果放入的元素小于輔助棧頂元素，輔助棧頂才 push，否則什么都不做
if not self.helper or self.helper[-1] > x:
self.helper.append(x)
def pop(self):
"""
:rtype: void
"""
if len(self.stack) == 0:
return
# 如果彈出的元素等于輔助棧棧頂元素，才將輔助棧頂元素彈出
if self.helper[-1] == self.stack[-1]:
self.helper.pop()
return self.stack.pop()
def top(self):
"""
:rtype: int
"""
return self.stack[-1]
def getMin(self):
"""
:rtype: int
"""
return self.helper[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
Java 代碼：
import java.util.Stack;
public class Solution {
private Stack<Integer> minStack = new Stack<>();
private Stack<Integer> dataStack = new Stack<>();
public void push(int node) {
if (minStack.isEmpty()) {
minStack.push(node);
dataStack.push(node);
return;
}
int curMin = minStack.peek();
if (node < curMin) {
minStack.push(node);
} else {
minStack.push(curMin);
}
dataStack.push(node);
}
public void pop() {
minStack.pop();
dataStack.pop();
}
public int top() {
return dataStack.pop();
}
public int min() {
return minStack.peek();
}
}
LeetCode 第 155 題：最小棧
設(shè)置一個輔助棧，保存當(dāng)前最小的元素。
class MinStack(object):
# 【特別注意】數(shù)據(jù)棧和輔助棧要同步，特殊測試用例為：
# 依次 push 0 1 0，馬上彈棧，查詢最小
def __init__(self):
"""
initialize your data structure here.
"""
# 數(shù)據(jù)棧
self.data_stack = []
# 輔助棧
self.help_stack = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.data_stack.append(x)
if len(self.help_stack) == 0 or x < self.help_stack[-1]:
self.help_stack.append(x)
else:
self.help_stack.append(self.help_stack[-1])
def pop(self):
"""
:rtype: void
"""
if len(self.data_stack) > 0:
ret = self.data_stack.pop()
self.help_stack.pop()
return ret
def top(self):
"""
:rtype: int
"""
if len(self.data_stack) > 0:
return self.data_stack[-1]
def getMin(self):
"""
:rtype: int
"""
if len(self.data_stack) > 0:
return self.help_stack[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
if __name__ == '__main__':
min_stack = MinStack()
min_stack.push(0)
min_stack.push(1)
min_stack.push(0)
print(min_stack.getMin())
min_stack.pop()
print(min_stack)
print(min_stack.getMin())
