【面試算法】一個有g(shù)etMin功能的棧

he_xd 發(fā)布于2019-08-14 15:17 / 1926人閱讀

摘要：題目實(shí)現(xiàn)一個特殊的棧，在實(shí)現(xiàn)棧的基本功能上再實(shí)現(xiàn)一個實(shí)現(xiàn)返回棧中最小元素的操作。要求，操作的時間復(fù)雜度都是，設(shè)計的棧類型額可以使用現(xiàn)成的棧結(jié)構(gòu)。第一種代碼實(shí)現(xiàn)第二種代碼實(shí)現(xiàn)

【題目】實(shí)現(xiàn)一個特殊的棧，在實(shí)現(xiàn)棧的基本功能上再實(shí)現(xiàn)一個實(shí)現(xiàn)返回棧中最小元素的操作。
【要求】
1，pop、push、getMin操作的時間復(fù)雜度都是O（1）；
2，設(shè)計的棧類型額可以使用現(xiàn)成的棧結(jié)構(gòu)。

第一種代碼實(shí)現(xiàn)：

public class GetMinStack_1 {

    private Stack stackData;
    private Stack stackMin;

    public GetMinStack_1(){
        stackData = new Stack();
        stackMin = new Stack();
    }

    public void push(int newNum){
        if (stackMin.isEmpty()) {
            stackMin.push(newNum);
        }else if (newNum <= getMin()) {
            stackMin.push(newNum);
        }
        stackData.push(newNum);
    }

    public int pop(){
        if (stackData.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        int value = stackData.pop();
        if (value == getMin()) {
            stackMin.pop();
        }
        return value;
    }

    private int getMin() {
        // TODO Auto-generated method stub
        if (stackMin.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        return stackMin.peek();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        GetMinStack_1 stack = new GetMinStack_1();
        int[] testNum = {4,2,4,6,5,0,1,10};
        for(int i:testNum){
            stack.push(i);
        }
        for(int i = 0; i < testNum.length; i++){
            System.out.println(stack.getMin()+" "+stack.pop());
        }
    }

}

第二種代碼實(shí)現(xiàn) ：

public class GetMinStack_2 {

    private Stack stackData;
    private Stack stackMin;

    public GetMinStack_2(){
        stackData = new Stack();
        stackMin = new Stack();
    }

    public void push(int newNum){
        if (stackMin.isEmpty()) {
            stackMin.push(newNum);
        }
        else if (newNum <= getMin()) {
            stackMin.push(newNum);
        }else {
            stackMin.push(getMin());
        }
        stackData.push(newNum);
    }

    public int pop(){
        if (stackData.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        int value = stackData.pop();
        stackMin.pop();
        return value;
    }

    private int getMin() {
        // TODO Auto-generated method stub
        if (stackMin.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        return stackMin.peek();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        GetMinStack_2 stack = new GetMinStack_2();
        int[] testNum = {4,2,4,6,5,0,1,10};
        for(int i:testNum){
            stack.push(i);
        }
        for(int i = 0; i < testNum.length; i++){
            System.out.println(stack.getMin()+" "+stack.pop());
        }
    }
}