跳转至

如何在O(1)内找到实时序列的最小值

本文总阅读量次 ,原创教程,严禁转载

最小栈

最小栈,能在O(1)内找到栈内序列的最小值,因此此特性经常用于提升算法性能。下面看看它的一种实现。

分析过程

  1. 入栈分析:

推入元素到 mainstack,只有当当前元素小于tmpstack栈顶(实际存储为mainstack中元素索引)元素时,才入栈到tmpstack,入栈的是索引。

假设mainstack当前有n个元素,则tmpstack内元素至多有n个。等于n时,表明原入栈序列为单调递减序列。

  1. 出栈分析:

元素从mainstack出栈,但要注意出栈元素索引是否等于tmpstack栈顶,若是需要将tmpstack栈顶元素出栈。可以预知,栈顶索引一定小于等于出栈元素(在mainstack栈内)的索引。

这道题需要注意两点:

  1. 临时栈里推送的是主栈的元素索引
  2. 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)的查询最小复杂度

    def getMin(self):
        """
        :rtype: int
        """

        if self.tmpstack:
            return self.mainstack[self.tmpstack[-1]]