剑指60题 | 面试题30. 包含min函数的栈 （Python实现）思路+问题版

思路：
1.栈的实现，有要求，时间复杂度是O(1)，学到普通栈的 push() 和 pop() 函数的复杂度分别为为 O(1)、O(1) ；而获取栈最小值 min() 函数需要遍历整个栈，复杂度为 O(N) ；
2.本题难点： 将 min() 函数复杂度降为 O(1) ，可通过建立辅助栈实现；
数据栈 mainStack ： 栈 mainStack 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
辅助栈 preStack ： 栈 preStack 中存储栈 mainStack 中所有 非严格降序 的元素，则栈 mainStack 中的最小元素始终对应栈 preStack 的栈顶元素，即 min() 函数只需返回栈 preStack 的栈顶元素即可。
因此，只需设法维护好 栈 preStack 的元素，使其保持非严格降序，即可实现 min() 函数的 O(1) 复杂度。
代码：

class MinStack:

    """
    【思路】：时间复杂度都为1的话就是链表了
    """
    def __init__(self):
        """
        initialize your data structure here.
        """
        head = None
        self.val = None

    def push(self, x: int) -> None:
        head = head.next
        return self.val.append(x)

    def pop(self) -> None:
        if self.val:
            return self.val
        else:
            return -1

    def top(self) -> int:
        if self.val:
            return self.val
        else:
            return -1

    def min(self) -> int:
        return min(self.val)


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.min()

【心得】：需要对逻辑结构再熟悉一些，比如栈、队列、树、堆的定义和特点使用，也就是方法实现。