《剑指offer》Java实现--包含Min函数的栈

题目描述

    自定义一个栈结构，包含push(),pop(),和getMin()三个函数，getMin用于获取栈中数据的最小值，要求时间复杂度均为O(1)。

思路分析

    拿到这个题目可能首先想到的是，定义一个辅助变量记录当前状态下的最小值，但是如果最小值被弹出了怎么办呢？我们无法在O(1)时间复杂度下找到新的最小值。因此我们可以考虑定义一个辅助栈，同步存下每个状态下的最小值。以空间换时间，这是算法设计中最常见的思想！

Java代码实现

import java.util.Stack;

/**
 * 实现一个栈，包含pop,push以及函数min获取栈中的最小值，时间复杂度均为O(1)
 * @author Administrator
 * @version 2018/10/12
 */
public class Exe32_StackWithMin {
    
    public static void main(String[] args) {
        MyStack testStack=new MyStack();
        testStack.push(1.0);
        testStack.push(2.0);
        testStack.push(1.5);
        testStack.push(3.0);
        System.out.println("the min value is "+testStack.getMin());
        System.out.println("the top value is "+testStack.pop());
    }
    
}

class MyStack{
    
    //数据栈
    Stack<Double> dataStack=new Stack<Double>();
    //最小值栈
    Stack<Double> minStack=new Stack<Double>();
    
    public synchronized void push(Double data) {
        dataStack.push(data);
        if(minStack.isEmpty()){
            minStack.push(data);
        }else {
            minStack.push(Math.min(minStack.peek(), data));
        }
    }
    
    public synchronized Double pop() {
        if(dataStack.isEmpty()||minStack==null){
            return null;
        }else {
            if(minStack.pop()!=null){
                return dataStack.pop();
            }else {
                return null;
            }
        }
    }
    
    public synchronized Double getMin() {
        if(minStack.isEmpty()){
            return null;
        }else {
            return minStack.peek();
        }
    }
    
}