LeetCode 155、最小栈

一、题目描述

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

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

二、题目解析

由于需要在常数时间内找到最小的元素，那么说明肯定是不能使用遍历，因为遍历是 O(n) 级别的时间，那么只能使用辅助空间进行存储，这是一种空间换时间的思想。

这里我们设置两个栈：普通栈和辅助栈。

**1、**push 操作

普通栈：直接添加 push 进来的值

辅助栈：每次 push 一个新元素的时候，将普通栈中最小的元素 push 进辅助栈中

**2、**pop 操作

普通栈：直接移除普通栈中的栈顶元素

辅助栈：判断普通栈中刚刚移除的栈顶元素值是否和此时辅助栈中的栈顶元素相同，如果是则将辅助栈中的栈顶元素移除，否则不执行操作，这样的目的是为了让辅助栈中的栈顶元素始终是普通栈中的最小值。

3、top 操作

普通栈：返回普通栈的栈顶元素

辅助栈：不执行操作

4、getMin 操作

普通栈：不执行操作

辅助栈：返回辅助栈的栈顶元素

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class MinStack {
    // 首先定义好两个栈

    // 一个栈叫做 stack，负责栈的正常操作
    Stack<Integer> stack;
    // 一个栈叫做 minStack，负责获取 stack 中的最小值，它等价于遍历 stack 中的所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈
    Stack<Integer> minStack;

    public MinStack() {
        // 在这个函数中初始化两个栈，传入的参数为空，返回也为空

        // 初始化 stack
        stack = new Stack<>();

        // 初始化 minStack
        minStack = new Stack<>();

    }

    public void push(int x) {
        // 新添加的元素添加到 stack 中
        stack.push(x);

        // 判断 minStack 是否为空，如果为空，直接同时把新添加的元素添加到 minStack 中

        // 如果 minStack 不为空
        if (!minStack.isEmpty()) {
            // 获取 minStack 的栈顶元素
            int top = minStack.peek();
            // 只有新添加的元素不大于 top 才允许添加到 minStack 中，目的是为了让 minStack 从栈底到栈顶是降序的
            if (x <= top) {
                // 此时，新添加的元素 x 小于 top，加入到 minStack 后依旧是从栈底到栈顶是降序的
                minStack.push(x);
            }
        }else{
            // 此时，minStack 中没有元素，所以直接把新添加的元素添加到 minStack 中
            minStack.push(x);
        }
    }

    public void pop() {
        
        // 让 stack 执行正常的 pop 操作就行
        int pop = stack.pop();

        // 由于 minStack 中的所有元素都是来自于 stack 中，所以 stack 删除元素后，minStack 也要考虑是否需要删除元素
        // 否则的话，minStack 有可能保存一个 stack 中不存在的元素

        // 首先，获取 minStack 的栈顶元素
        int top = minStack.peek();
        // 再判断 top 这个栈顶元素是否和 stack 移除的元素相等，如果相等，那么需要把 minStack 中的栈顶元素一并移除 
        if (pop == top) {
            // 移除 minStack 的栈顶元素
            minStack.pop();
        }

    }

    public int top() {
        // 返回 stack 的栈顶元素
        return stack.peek();
    }

    public int getMin() {
        // 返回 minStack 的栈顶元素
        return minStack.peek();
    }
}

2、C++代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 最小栈（ LeetCode 155 ）:https://leetcode-cn.com/problems/min-stack/
class MinStack {
public:
    // 首先定义好两个栈

    // 一个栈叫做 stk
    stack<int> stk;

    // 一个栈叫做 minstk，负责获取 stk 中的最小值，它等价于遍历 stk 中的所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈
    stack<int> minstk;

    MinStack() {    
  
    }

    void push(int x) {
        // 新添加的元素添加到 stk 中
        stk.push(x);

        // 判断 minstk 是否为空，如果为空，直接同时把新添加的元素添加到 minstk 中

        // 如果 minstk 不为空
        if (!minstk.empty()) {
            // 获取 minstk 的栈顶元素
            int top = minstk.top();
            // 只有新添加的元素不大于 top 才允许添加到 minstk 中，目的是为了让 minstk 从栈底到栈顶是降序的
            if (x <= top) {
                // 此时，新添加的元素 x 小于 top，加入到 minstk 后依旧是从栈底到栈顶是降序的
                minstk.push(x);
            }
        }else{
            // 此时，minstk 中没有元素，所以直接把新添加的元素添加到 minstk 中
            minstk.push(x);
        }
    }

    void pop() {
        
        // 让 stk 执行正常的 pop 操作就行
        int pop = stk.top();

        stk.pop();

        // 由于 minstk 中的所有元素都是来自于 stk 中，所以 stk 删除元素后，minstk 也要考虑是否需要删除元素
        // 否则的话，minstk 有可能保存一个 stk 中不存在的元素

        // 首先，获取 minstk 的栈顶元素
        int top = minstk.top();
        // 再判断 top 这个栈顶元素是否和 stk 移除的元素相等，如果相等，那么需要把 minstk 中的栈顶元素一并移除 
        if (pop == top) {
            // 移除 minstk 的栈顶元素
            minstk.pop();
        }

    }

    int top() {
        // 返回 stk 的栈顶元素
        return stk.top();
    }

    int getMin() {
        // 返回 minstk 的栈顶元素
        return minstk.top();
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 最小栈（ LeetCode 155 ）:https://leetcode-cn.com/problems/min-stack/
class MinStack:
    def __init__(self):
        # 首先定义好两个栈

        # 一个栈叫做 stack，负责栈的正常操作
        self.stack = []

        # 一个栈叫做 min_stack，负责获取 stack 中的最小值，它等价于遍历 stack 中的所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈
        self.min_stack = []

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

        # 新添加的元素添加到 stack 中
        self.stack.append(x)

        # 判断 min_stack 是否为空，如果为空，直接同时把新添加的元素添加到 minStack 中
        # 如果 min_stack 不为空
        if self.min_stack:
           # 获取 min_stack 的栈顶元素
           top = self.min_stack[-1]

           # 只有新添加的元素不大于 top 才允许添加到 minStack 中，目的是为了让 minStack 从栈底到栈顶是降序的
           if x <= top :
              self.min_stack.append(x)

        # min_stack 中没有元素，所以直接把新添加的元素添加到 min_stack 中
        else:
            self.min_stack.append(x)


    def pop(self) -> None:

        # 让 stack 执行正常的 pop 操作就行
        pop =  self.stack[-1]

        self.stack.pop()

        # 由于 minStack 中的所有元素都是来自于 stack 中，所以 stack 删除元素后，minStack 也要考虑是否需要删除元素
        # 否则的话，minStack 有可能保存一个 stack 中不存在的元素

        # 首先，获取 minStack 的栈顶元素
        top = self.min_stack[-1]

        # 再判断 top 这个栈顶元素是否和 stack 移除的元素相等，如果相等，那么需要把 minStack 中的栈顶元素一并移除 
        if pop == top:
            # 移除 min_stack 的栈顶元素
            self.min_stack.pop()

    def top(self) -> int:
        # 返回 stack 的栈顶元素
        return self.stack[-1]
    def getMin(self) -> int:
        # 返回 min_stack 的栈顶元素
        return self.min_stack[-1]

四、复杂度分析

时间复杂度：对于题目中的所有操作，时间复杂度均为 O(1)。因为栈的插入、删除与读取操作都是 O(1)，我们定义的每个操作最多调用栈操作两次。

空间复杂度：O(n)，其中 n 为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 O(n)。