🥉03.02. 栈的最小值

请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

示例：

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

思路（Python）

个人思路

想起来挺简单的，直接用list不就行了吗？但是其中的list里面的min时间复杂度是O(n),下面的代码能过，但是是不对的！

class MinStack:

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


    def push(self, x: int) -> None:
        self.stack.append(x)


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


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


    def getMin(self) -> int:
        return min(self.stack)



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

那既然要取栈最小值，为什么不可以设置栈的一个参数min来记录栈的最小值呢？代码也很简单：

import sys
class MinStack:

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


    def push(self, x: int) -> None:
        self.stack.append(x)
        if x<=self.minx:
            self.minx=x


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

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


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

但是写出代码一想不对啊，如果栈push进来了[2,3,1]，那minx就是1，但是如果再执行一个pop，minx就不应该是1了，而是2。这里的minx没有更新，所以是错的。但要再更新minx，时间复杂度就不是$O(1)$了，所以这样不行！

正确的思路

方法1

leetcode

使用一个主栈模拟入栈出栈的操作，然而，为了使 getMin 函数实现 $O(1)$ 的时间复杂度，我们可以使用另一个栈来实现。

我们可以将这个栈称为最小栈，每当入栈的数小于等于栈顶元素时，随主栈都进行一次 push 操作；

当出栈的数与最小栈的栈顶元素相等时，最小栈也随主栈进行一次 pop 操作。

class MinStack:

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


    def push(self, x: int) -> None:
        self.stack.append(x)
        if len(self.minstack)==0 or x <= self.minstack[-1]:
            self.minstack.append(x)


    def pop(self) -> None:
        a=self.stack.pop()
        if a==self.minstack[-1]:
            self.minstack.pop()


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


    def getMin(self) -> int:
        if len(self.minstack)==0:
            return None
        return self.minstack[-1]

方法二

上面是用两个栈操作的，还是有点麻烦，但能不能用一个栈？但是之前也试过，不行。要在上面的基础上改进一下：

之前的问题是minx更新之后，之前的minx就丢了，但这里还需要继续用，因为minx有可能被pop出去。

那怎么保存之前的minx呢？只需要在更新minx之前把它压入栈里面：

入栈 2 ，同时将之前的 min 值 3 入栈，再把 2 入栈，同时更新 min = 2
| 2 |   min = 2
| 3 |  
| 5 |     
|_3_|    
stack  

入栈 6 
| 6 |  min = 2
| 2 |   
| 3 |  
| 5 |     
|_3_|    
stack  

出栈 6     
| 2 |   min = 2
| 3 |  
| 5 |     
|_3_|    
stack  

出栈 2     
| 2 |   min = 2
| 3 |  
| 5 |     
|_3_|    
stack

上边的最后一个状态，当出栈元素是最小元素我们该如何处理呢？

我们只需要把 2 出栈，然后再出栈一次，把 3 赋值给 min 即可。

出栈 2     
|   |  min = 3   
| 5 |   
|_3_|    
stack

通过上边的方式，我们就只需要一个栈了。当有更小的值来的时候，我们只需要把之前的最小值入栈，当前更小的值再入栈即可。当这个最小值要出栈的时候，下一个值便是之前的最小值了。

import sys
class MinStack:

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


    def push(self, x: int) -> None:
        # 如果新加入比minx要小，就把minx再压入栈一次
        if x<=self.minx:
            self.stack.append(self.minx)
            self.minx=x
        self.stack.append(x)



    def pop(self) -> None:
        a=self.stack.pop()
        # 如果要pop出的是minx，就把minx先pop出来，栈顶部剩下的就是之前的两个minx
        # 先pop掉一个，剩下的栈顶就是minx
        if a==self.minx: 
            self.minx=self.stack.pop()

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


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

直接用一个链表即可实现栈的基本功能，那么最小值该怎么得到呢？我们可以在 Node 节点中增加一个 min 字段，这样的话每次加入一个节点的时候，我们同时只要确定它的 min 值即可。

代码很简洁。

class MinStack {
    class Node{
        int value;
        int min;
        Node next;

        Node(int x, int min){
            this.value=x;
            this.min=min;
            next = null;
        }
    }
    Node head;
    //每次加入的节点放到头部
    public void push(int x) {
        if(null==head){
            head = new Node(x,x);
        }else{
            //当前值和之前头结点的最小值较小的做为当前的 min
            Node n = new Node(x, Math.min(x,head.min));
            n.next=head;
            head=n;
        }
    }

    public void pop() {
        if(head!=null)
            head =head.next;
    }

list的时间复杂度

下面是python list的时间复杂度：