題目
設計一個支持 push，pop，top 操作，并能在常數時間內檢索到最小元素的堆疊，
push(x) -- 將元素 x 推入堆疊中，
pop() -- 洗掉堆疊頂的元素，
top() -- 獲取堆疊頂元素，
getMin() -- 檢索堆疊中的最小元素，
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 回傳 -3.
minStack.pop();
minStack.top(); --> 回傳 0.
minStack.getMin(); --> 回傳 -2.
思路
設計時使用兩個堆疊
一個堆疊用來保存當前堆疊中的元素，記為stack_data
一個堆疊用于保存每一步的最小值，記為stack_min
方案一
新元素x入堆疊
1.資料x將要入堆疊，先入堆疊stack_data
2.判斷堆疊stack_min是否為空，為空x直接入stack_min，否則判斷stack_min堆疊頂元素和x的大小，如果x小于或者等于堆疊頂元素，則x入堆疊stack_min，大于則不做處理
3.獲取堆疊的最小值則回傳stack_min的堆疊頂元素
元素出堆疊
1.stack_data堆疊正常彈出堆疊頂元素y
2.判斷stack_data彈出的元素y與stack_min堆疊頂元素的大小，如果y等于堆疊頂元素，則stack_min也彈出堆疊頂元素
方案二
新元素x入堆疊
1.資料x將要入堆疊，先入堆疊stack_data
2.判斷堆疊stack_min是否為空，為空x直接入stack_min，否則判斷stack_min堆疊頂元素和x的大小，如果x小于或者等于堆疊頂元素，則x入堆疊stack_min，大于的話則把stack_min的堆疊頂元素重復壓入stack_min
元素出堆疊
1.stack_data堆疊正常彈出堆疊頂元素y
2.stack_min堆疊正常彈出堆疊頂元素z
3.獲取堆疊的最小值則回傳stack_min的堆疊頂元素
代碼
方案一
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack_data = []
self.stack_min = []
def push(self, x: int) -> None:
self.stack_data.append(x)
if self.stack_min:
if x <= self.stack_min[-1]:
self.stack_min.append(x)
else:
self.stack_min.append(x)
def pop(self) -> None:
if self.stack_data and self.stack_min:
if self.stack_min[-1] == self.stack_data.pop():
self.stack_min.pop()
def top(self) -> int:
if self.stack_data:
return self.stack_data[-1]
def getMin(self) -> int:
if self.stack_min:
return self.stack_min[-1]
方案二
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack_data = []
self.stack_min = []
def push(self, x: int) -> None:
self.stack_data.append(x)
if self.stack_min:
if x <= self.stack_min[-1]:
self.stack_min.append(x)
else:
self.stack_min.append(self.stack_min[-1])
else:
self.stack_min.append(x)
def pop(self) -> None:
if self.stack_data and self.stack_min:
self.stack_data.pop()
self.stack_min.pop()
def top(self) -> int:
if self.stack_data:
return self.stack_data[-1]
def getMin(self) -> int:
if self.stack_min:
return self.stack_min[-1]
復雜度分析
方案一
- 時間復雜度：O(1)，“出堆疊”、“入堆疊”、“查看堆疊頂元素”的操作和資料量的多少無關，都是有限的步驟
- 空間復雜度：O(n)
- 方案一壓入時稍省空間，彈出稍費時間
方案二
- 時間復雜度：O(1)，“出堆疊”、“入堆疊”、“查看堆疊頂元素”的操作和資料量的多少無關，都是有限的步驟
- 空間復雜度：O(n)
- 方案二壓入時稍費空間，彈出稍省時間
公眾號:《程式員養成記》
主要寫演算法、計算機基礎之類的文章, 有興趣來關注一起成長！
著作權宣告 :著作權歸作者所有，非商業轉載請注明出處，禁止商業轉載，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/124293.html
標籤：其他
下一篇：采用鄰接矩陣表示法創建無向網