目录

• 1、题目描述：
• 2、方法：
• • 思路：
  • 代码：

1、题目描述：

2、方法：

思路：

思路来源：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution/mian-shi-ti-30-bao-han-minhan-shu-de-zhan-fu-zhu-z/

普通栈的 p u s h ( ) push() push() 和 p o p ( ) pop() pop() 函数的复杂度为 O ( 1 ) O(1) O(1) ，而获取栈最小值 m i n ( ) min() min() 函数需要遍历整个栈，复杂度为 O ( N ) O(N) O(N)。

本题难点在于： 将 min() 函数复杂度降为 O ( 1 ) O(1) O(1) ，可通过建立辅助栈实现。细节下面一一说来：

数据栈 A A A ： 栈 A A A 用于存储所有元素，保证入栈 p u s h ( ) push() push() 函数、出栈 p o p ( ) pop() pop() 函数、获取栈顶 t o p ( ) top() top() 函数的正常逻辑。
辅助栈 B B B ： 栈 B B B 中存储栈 A A A 中所有 非严格降序 的元素，则栈 A A A 中的最小元素始终对应栈 B B B 的栈顶元素，即 m i n ( ) min() min() 函数只需返回栈 B B B 的栈顶元素即可。

因此，只需设法维护好 栈 B B B 的元素，使其保持非严格降序，即可实现 m i n ( ) min() min() 函数的 O ( 1 ) O(1) O(1) 复杂度。如下图所示：

如果还有点懵逼，下面我说一下具体的做法就知道怎么回事了：

• 当元素入栈时，即执行 p u s h ( ) push() push()函数时，我们将元素压入数据栈 A A A中，同时检查当前辅助栈 B B B的情况：辅助栈 B B B为空或者当前要 p u s h ( ) push() push()的元素小于等于辅助栈 B B B栈顶的元素，则把当前元素也压入辅助栈 B B B。
• 当元素出栈时，我们把数据栈 A A A栈顶的元素弹出，同时检查数据栈 A A A栈顶元素是不是等于辅助栈 B B B栈顶元素，如果等于，则把辅助栈 B B B栈顶元素也出栈。

代码：

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stackA = [] # 数据栈
        self.stackB = [] # 辅助栈


    def push(self, x: int) -> None:
        self.stackA.append(x)
        if not self.stackB or self.stackB[-1] >= x:
            self.stackB.append(x) # 如果stackB为空,或者x小于等于栈顶元素,则x直接入stackB


    def pop(self) -> None:
        # 栈B中存储栈A中所有非严格降序的元素，则栈A中的最小元素始终对应栈B的栈顶元素
        if self.stackA.pop() == self.stackB[-1]:
            self.stackB.pop()


    def top(self) -> int:
        return self.stackA[-1] # 栈顶元素


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


# 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()