Jianbo Dai's

jz030.包含min函数的栈

 
  • Jun 10, 2020

题目链接

这个问题，难点在于min函数的设计，对于这个函数，我们的第一反应可能会是用一个元素存放最小的元素， 并在新元素被压入栈时更新变量，然后在调用min函数时将相应元素返回。但是，这种设计带来的问题就是，如果当前最小的元素被弹出栈了，那么如何得到下一个最小的元素？分析到这里我们会发现，仅仅用一个额外的成员变量来保存最小元素是不够的，那是否可以用一个辅助栈来保存每次最小的元素呢？算法1实现的就是这种思路。这个算法的时间复杂度是O（1），空间复杂度是O（N）。

但是，这个设计仍在辅助栈里保存了一些多余的元素，那就是不需要在每次元素入栈的时候在辅助栈中添加元素，只有当最小元素发生改变时才在辅助栈里加新元素。当调用min函数时，若mainStack中要弹出的元素是当前最小的元素的时候，才也将auxiliary中的元素弹出。这样，可以省去很多多余的操作。

class MinStack1:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.mainStack, self.auxillaryStack = [], []

    def push(self, x: int):
        self.mainStack.append(x)
        if len(self.auxillaryStack) == 0 or x <= self.auxillaryStack[-1]:
            self.auxillaryStack.append(x)
        else:
            self.auxillaryStack.append(self.auxillaryStack[-1])

    def pop(self) -> None:
        assert (len(self.mainStack) > 0 and len(self.auxillaryStack) > 0)
        self.auxillaryStack.pop()
        return self.mainStack.pop()

    def top(self) -> int:
        return self.mainStack[-1]

    def min(self) -> int:
        return self.auxillaryStack[-1]


class MinStack2:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.mainStack, self.auxillaryStack = [], []

    def push(self, x: int):
        self.mainStack.append(x)
        if not self.auxillaryStack or x <= self.auxillaryStack[-1]:
            self.auxillaryStack.append(x)

    def pop(self) -> None:
        assert (len(self.mainStack) > 0 and len(self.auxillaryStack) > 0)
        if self.mainStack[-1] == self.auxillaryStack[-1]:
            self.auxillaryStack.pop()
        return self.mainStack.pop()

    def top(self) -> int:
        return self.mainStack[-1]

    def min(self) -> int:
        return self.auxillaryStack[-1]
Search