剑指 Offer 30. 包含min函数的栈

题目描述

https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop、top的时间复杂度都是 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.

提示：

各函数的调用总次数不超过 20000 次

解题思路

push可以用append()实现；
top可以用arr[-1]实现(返回top指向的值)；
pop可以用pop()实现；
那么min怎么在O(1)内实现呢？
可以建立一个辅助栈B实现min。平时的push、top、pop操作都针对A执行。在压进A栈时，记录当前压入的数是不是A栈里面压过的最小值，如果是，就把这个数也压进B。这样，B的top就一直是A栈中压过的数的最小值。所谓的min实际上就是B[-1]。

解题代码

class MinStack:
    def __init__(self):
        self.A, self.B = [], []

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

    def pop(self) -> None:
        if self.A.pop() == self.B[-1]:
            self.B.pop()

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

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

执行结果

执行结果：通过
执行用时：68 ms, 在所有 Python3 提交中击败了57.44%的用户
内存消耗：18 MB, 在所有 Python3 提交中击败了41.67%的用户