LeetCode初級演算法--設計問題02：最小堆疊
搜索微信公眾號:'AI-ming3526'或者'計算機視覺這件小事' 獲取更多演算法、機器學習干貨
csdn：https://blog.csdn.net/baidu_31657889/
csdn：https://blog.csdn.net/abcgkj/
github：https://github.com/aimi-cn/AILearners
一、引子
這是由LeetCode官方推出的的經典面試題目清單~
這個模塊對應的是探索的初級演算法~旨在幫助入門演算法，我們第一遍刷的是leetcode推薦的題目，
查看完整的劍指Offer演算法題決議請點擊github鏈接：
github地址
二、題目
設計一個支持 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.
1、思路
第一種方法：
用串列模擬堆疊，push、pop、top和getMin分別對應list.append()、list.pop()、list[-1]和min()操作
第二種方法：
引入minStack串列存放最小值
2、編程實作
第一種方法：
python
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.l = []
def push(self, x):
"""
:type x: int
:rtype: None
"""
if x is None:
pass
else:
self.l.append(x)
def pop(self):
"""
:rtype: None
"""
if self.l is None:
return 'error'
else:
self.l.pop(-1)
def top(self):
"""
:rtype: int
"""
if self.l is None:
return 'error'
else:
return self.l[-1]
def getMin(self):
"""
:rtype: int
"""
if self.l is None:
return 'error'
else:
return min(self.l)
# 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()
第二種方法：
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = [] #存放所有元素
self.minStack = []#存放每一次壓入資料時，堆疊中的最小值（如果壓入資料的值大于堆疊中的最小值就不需要重復壓入最小值，小于或者等于堆疊中最小值則需要壓入）
def push(self, x):
"""
:type x: int
:rtype: void
"""
self.stack.append(x)
if not self.minStack or self.minStack[-1]>=x:
self.minStack.append(x)
def pop(self): #移除堆疊頂元素時，判斷是否移除堆疊中最小值
"""
:rtype: void
"""
if self.minStack[-1]==self.stack[-1]:
del self.minStack[-1]
self.stack.pop()
def top(self):
"""
:rtype: int
"""
return self.stack[-1]
def getMin(self):
"""
:rtype: int
"""
return self.minStack[-1]
AIMI-CN AI學習交流群【1015286623】 獲取更多AI資料
分享技術，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關注！
本文由博客一文多發平臺 OpenWrite 發布！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65623.html
標籤：其他