剑指Offer-包含min函数的栈

发表于 | 阅读次数 | 阅读数

包含min函数的栈

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

思路

1.第一思路是每次都更新一个最小值，但是问题是：最小值弹完了咋更新呢。
2.第二思路再用一个栈来保存更新的值。弹出的话也能弹出。之前的值也都在。保存更新minStack
  的时候如果当前的值比minstack的top值大的时候，top值再入一次栈

代码

public class minStack {
    public Stack<Integer> dataStack;//数据栈
    public Stack<Integer> minStack;//最小值栈


    public minStack(){
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }

    /**
     * 一个正常存值，一个每次都存当前最小的min或者存新的小node，不管什么样子都要存一个值。
     * @param node
     */
    public void push(int node){
        dataStack.push(node);
        if (minStack.isEmpty()){
            minStack.push(node);
        }else if(node < this.min()){
            minStack.push(node);
        }else {
            int temp = minStack.peek();//存
            minStack.push(temp);
        }
    }

    public void pop(){
        dataStack.pop();
        minStack.pop();
    }

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

    public int min(){
        if (minStack.isEmpty()){
            throw new RuntimeException("empty");
        }
        return minStack.peek();
    }

}
0%