剑指Offer[30]-包含min函数的栈

题目

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

python代码

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.main_list = []
        self.min_list = []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.main_list.append(x)
        if len(self.min_list)==0 or x <= self.min_list[-1]:
            self.min_list.append(x)

    def pop(self):
        """
        :rtype: None
        """
        if len(self.main_list)>0:
            val = self.main_list.pop()
            if val == self.min_list[-1]:
                self.min_list.pop()

    def top(self):
        """
        :rtype: int
        """
        if len(self.main_list)>0:
            val = self.main_list[-1]
            return val
        else:
            return None

    def min(self):
        """
        :rtype: int
        """
        if len(self.min_list)>0:
            return self.min_list[-1]
        else:
            return None

这道题主要考察怎么构建一个最小栈,因为需要在O(1)的时间复杂度下查找最小值,所以需要在push操作时就完成最小值的判断与储存,这里我们使用了额外的列表来维护“局部最小值”关系,主要思路在push函数中:

  • 当有新元素时,首先插入到主列表main_list中;
  • 再判断新元素是否小于之前的最小值,若小于则同时插入到min_list中,反之,不插入到min_list中。

同时在pop函数中还要注意:

  • 先从main_list中弹出元素,然后判断是否与min_list[-1]相同(相同的话,相当于当前弹出的元素为当前main_list的最小值),若相同,则需要同时弹出min_list[-1]。

举个例子:

  • 分别push -2,0,3,则main_list为[-2,0,-3],min_list为[-2,-3];
  • 执行一次pop,main_list为[-2,0],min_list为[-2];
  • 执行一次pop,main_list为[-2],min_list为[-2];

发表评论

电子邮件地址不会被公开。