剑指 Offer 30. 包含min函数的栈-2021/12/28

# 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
    示例:	
    	MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        minStack.min();   --> 返回 -3.
        minStack.pop();
        minStack.top();      --> 返回 0.
        minStack.min();   --> 返回 -2.
    提示：
    	1.各函数的调用总次数不超过 20000 次

题目解读:

• 获取栈的最小值min()需要遍历整个栈，复杂度为O(n)，需要将min()函数的复杂度降为O(1)。

解题思路:

• 辅助栈:

1.  栈stack1存储所有元素
   

2. 栈stack2存储stack1中所有非严格递减的元素	
   

• push()函数：保证填充stack1，及填充栈stack2非严格递减元素
• pop()函数：当stack1与stack2顶部值相同时，同时弹出。保证stack1与stack2元素的一致性
• top()函数返回stack1的顶部元素
• min()函数返回最小值

Java代码:

import java.util.Stack;

public class MinStack {
    Stack stack1,stack2;
    // 初识化
    public MinStack(){
        stack1 = new Stack();
        stack2 = new Stack();
    }
    
    public void push(int x){
        stack1.push(x);
        if(stack2.isEmpty() || stack2.peek()>=x){
            stack2.push(x);
        }
    }
    //弹出stack1与stack2的最小值  保持两栈元素的一致性
    public void pop(){
        if(stack1.pop().equals(stack2.peek())){
            stack2.pop();
        }
    }
    // 返回栈stack1的顶部元素
    public int top(){
        return stack1.peek();
    }
    // 返回栈的最小值
    public int min(){
        return stack2.pop();
    }
// 测试
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.min());
        minStack.pop();
        System.out.println( minStack.top());
        System.out.println(minStack.min());
    }

}

Java 代码中，由于 Stack 中存储的是 int 的包装类 Integer ，因此需要使用 equals() 代替 == 来比较值是否相等。