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

最小棧

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

分析過程

1. 入棧分析：

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

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

2. 出棧分析:

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

這道題需要注意兩點(diǎn)：

1. 臨時(shí)棧里推送的是主棧的元素索引

2. push時(shí)若臨時(shí)棧為空，需要先推入此元素在主棧索引

代碼

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]]