描述

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)

push(value):将value压入栈中

pop():弹出栈顶元素

top():获取栈顶元素

min():获取栈中最小元素

示例

输入：
 ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
返回值：
-1,2,1,-1

知识点：模拟、栈

难度：⭐⭐

题解

图解：

方法一：模拟栈

算法流程：

• 维护一个全局变量保存stack当前栈中的最小元素的值
• push过程：
  • 栈中没有数据，最小元素min直接初始化
  • 栈中有数据：
    • 新增元素小于等于min则更新最小值min，同时加入min和新元素
    • 新增元素大于min则直接push新元素
• pop过程：
  • 栈顶元素为最小元素时，如果栈中除了min还有其他元素，则更新最小值，否则栈中只有min，则重新初始化
  • 否则直接pop栈顶元素
• top直接pop栈顶元素
• min直接返回全局变量min

Java 版本代码如下：

import java.util.Stack;

public class Solution {
    // 全局变量保存stack当前栈中的最小元素的值
    static int min = Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<>();
    public void push(int node) {
        // 栈中没有数据，最小元素min直接初始化
        if(stack.isEmpty()) {
            min = node;
            stack.push(node);
        } else {
            // 新增元素小于等于min则更新最小值min，同时加入min和新元素
            if(node <= min) {
                // 保证在pop的时候，如果栈顶元素是min时，在pop min后能让min获得新的最小元素
                stack.push(min);
                min = node;
            }
            // 新增元素大于min则直接push新元素
            stack.push(node);
        }
    }

    public void pop() {
        if(stack.isEmpty()) {
            return;
        }
        // 栈顶元素为最小元素时
        if(min == stack.peek()) {
            // 如果栈中除了min还有其他元素，则更新最小值
            if(stack.size() > 1){
                stack.pop();
                min = stack.peek();
            } else {
                // 栈中只有min，则重新初始化
                min = Integer.MAX_VALUE;
            }
        }
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return this.min;
    }
}

复杂度分析：

时间复杂度 $O(1)O(1)$：pop、push、top、min都只需要常量时间 空间复杂度 $O(N)O(N)$：用到栈来保存元素

方法二：双栈

解题思路：

一个栈保存元素，另一个栈的栈顶一直保存最小元素

算法流程：

• 维护两个栈，一个栈保存元素，另一个栈的栈顶一直保存最小元素
• push过程：
  • stack直接新增元素
  • minStack为空，则新元素就是最小元素
  • minStack不为空时
    • 如果minStack栈顶元素，即当前栈中最小元素比新增元素大, 则加到栈顶，作为最新的栈最小元素
    • 否则加入栈顶元素，保证minStack元素数量与stack元素数量一致
• top返回stack栈顶元素，相对的min返回minStack栈顶元素，即最小元素

Java 版本代码如下：

import java.util.Stack;

public class Solution {
    // 保存所有元素
    Stack<Integer> stack = new Stack<Integer>();
    // 栈顶元素一直保存stack中的最小元素
    Stack<Integer> minStack = new Stack<Integer>();

    public void push(int node) {
        stack.push(node);
        // minStack为空，则新元素就是最小元素
        if(minStack.empty()){
            minStack.push(node);
        }else{
            // minStack不为空时
            // 如果minStack栈顶元素，即当前栈中最小元素比新增元素大
            // 则加到栈顶，作为最新的栈最小元素
            if(node <= minStack.peek()){
                minStack.push(node);
            }else{
                // 否则加入栈顶元素，保证minStack元素数量与stack元素数量一致
                minStack.push(minStack.peek());
            }
        }
    }

    public void pop() {
        // 保证minStack元素数量与stack元素数量一致
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minStack.peek();
    }
}

复杂度分析：

时间复杂度 $O(1)O(1)$：无需用到循环 空间复杂度 $O(N)O(N)$：需要用到栈保存元素