如何在O(1)內(nèi)找到實時序列的最小值

如何在O(1)內(nèi)找到實時序列的最小值，針對這個問題，這篇文章詳細介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

最小棧

最小棧，能在O(1)內(nèi)找到棧內(nèi)序列的最小值，因此此特性經(jīng)常用于提升算法性能。下面看看它的一種實現(xiàn)。

分析過程

入棧分析：

推入元素到  mainstack，只有當當前元素小于tmpstack棧頂(實際存儲為mainstack中元素索引)元素時，才入棧到tmpstack，入棧的是索引。

假設(shè)mainstack當前有n個元素，則tmpstack內(nèi)元素至多有n個。等于n時，表明原入棧序列為單調(diào)遞減序列。

出棧分析：

元素從mainstack出棧，但要注意出棧元素索引是否等于tmpstack棧頂，若是需要將tmpstack棧頂元素出棧?？梢灶A(yù)知，棧頂索引一定小于等于出棧元素(在mainstack棧內(nèi))的索引。

這道題需要注意兩點：

• 臨時棧里推送的是主棧的元素索引

• push時若臨時棧為空，需要先推入此元素在主棧索引

代碼

class MinStack(object):     def __init__(self):          """         initialize your data structure here.         """         self.mainstack= []         self.tmpstack = []

推入元素：

def push(self, val):      """     :type val: int     :rtype: None     """      self.mainstack.append(val)      if not self.tmpstack:          self.tmpstack.append(len(self.mainstack)-1)      # smaller than top of tmpstack     if self.mainstack[self.tmpstack[-1]] > val:          self.tmpstack.append(len(self.mainstack)-1)

出棧元素：

def pop(self):     """     :rtype: None     """      # min val of tmp stack equals top of mainstack     if self.tmpstack and self.tmpstack[-1] == len(self.mainstack)-1:         self.tmpstack.pop()      return self.mainstack.pop()

def top(self):     """     :rtype: int     """      if self.mainstack:         return self.mainstack[-1]

使用tmpstack輔助棧，換來了O(1)的查詢最小復(fù)雜度

def getMin(self):     """     :rtype: int     """      if self.tmpstack:         return self.mainstack[self.tmpstack[-1]]

關(guān)于如何在O(1)內(nèi)找到實時序列的最小值問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。