每日一道算法之--最小栈

栈

Word count: 980Reading time: 4 min

 2020/03/14   Share

最小栈

力扣第155题 : https://leetcode-cn.com/problems/min-stack/

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
top() – 获取栈顶元素。
getMin() – 检索栈中的最小元素。
示例:

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

最开始的思路

当我看到这道题的时候,因为是求最小的元素,所以我只用了一个变量,想要动态的更新最小值。但是有一个问题就出现了，当我把最小值pop出来后，当前的最小值就又会发生变化了，所以用变量保存最小值不是一个理想的解法。我又想到了再用一个数组来保存最小的的变化信息，当pop的时候在更新最小值。

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_ele = float('inf')
        self.min_list = []
    def push(self, x: int) -> None:
        self.stack.append(x)
        self.min_ele = min(self.min_ele, x)
        if self.min_ele not in self.min_list:
            self.min_list.append(self.min_ele)

    def pop(self) -> None:
        pop_ele = self.stack.pop()
        if self.min_ele == pop_ele and pop_ele not in self.stack:
            self.min_list.pop()
        if self.min_list:
            self.min_ele = self.min_list[-1]

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

    def getMin(self) -> int:
        return self.min_ele

虽然没通过,但是辅助栈的雏形已经出来了

1. 同步的辅助栈

上面的代码其实存储最小值的变量是没必要的,因为最小值已经存储在辅助栈里面了
当我们在push入栈的时候,同时将该数和辅助栈的栈顶元素比较大小,如果小于栈顶元素,则最小值为该元素,将该元素push入辅助栈中;如果大于栈顶元素,则证明最小值仍为栈顶元素
从而实现了主栈和辅助栈永远是同步的,即长度一样,级主栈中每一个元素对应的栈中最小值是正确的.

class MinStack:

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


    def push(self, x: int) -> None:
        self.stack.append(x)
        # 主要逻辑就是在这里
        if not self.min_stack or self.min_stack[-1] > x:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> None:
        if self.stack:
            self.stack.pop()
            self.min_stack.pop()

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

    def getMin(self) -> int:
        if self.min_stack:
            return self.min_stack[-1]

1.1 复杂度分析

时间复杂度：，“出栈”、“入栈”、“查看栈顶元素”的操作不论数据规模多大，都只是有限个步骤，因此时间复杂度是：O(1)。

空间复杂度：O(N)，这里 N 是读出的数据的个数。

2. 不同步的辅助栈

同步辅助栈虽然很好理解,但是有一个问题就是它为了保持长度跟主栈一样,从而造成了没必要的浪费,所以这里讲一下不同步的辅助栈。

不同步辅助栈就是只有在push时该数小于或等于辅助栈的栈顶元素是才push入辅助栈
在pop元素之，如果该元素等于辅助栈的栈顶元素，则将辅助栈的栈顶元素pop出来

class MinStack:

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


    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or self.min_stack[-1] >= x:
            self.min_stack.append(x)

    def pop(self) -> None:
        if self.stack:
            top = self.stack.pop()
            if self.min_stack and top == self.min_stack[-1]:
                self.min_stack.pop()

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

    def getMin(self) -> int:
        if self.min_stack:
            return self.min_stack[-1]