栈面试题实现查找最小栈元素

1.实现一个特殊的栈，在栈的基本功能基础上，再实现返回栈中最小元素的的操作getMin。

要求

1.pop，push，getMin操作的时间复杂度为O(1)
2.设计的栈类型可以使用现成的栈类型。

解决方法1：

以栈内元素 3，4，1，2，5为例 依次入栈
记住一个基本规则，只有当前数小于等于StackMin栈顶元素时，该数才可以放入StackMin

步骤：

1. 3 入栈 ， StackMin为空，将该数分别放入俩栈中。
2. 4入栈 ， 4 > 此时的栈StackMin的栈顶元素3，不压入
3. 1 入栈 ， 1 < 此时的栈StackMin的栈顶元素3 1进栈
4. 2 入栈 ， 2 > 此时的栈StackMin的栈顶元素1，不压入
5. 5入栈 ， 5>此时的栈StackMin的栈顶元素1，不压入

如图所示：

解决方法2：

和方法一比较相似，区别在于，方法1 如果元素大于StackData栈顶元素则不选择压入
而区别在于方法2，元素大于StackMin栈顶元素不选择不压入，而是选择将StartMin的栈顶元素压入

步骤：

1. 3 入栈 ， StackMin为空，将该数分别放入俩栈中。
2. 4入栈 ， 4 > 此时的栈StackMin的栈顶元素3，压入StackMin栈顶元素3
3. 1 入栈 ， 1 < 此时的栈StackMin的栈顶元素3 1进栈
4. 2 入栈 ， 2 > 此时的栈StackMin的栈顶元素1，压入StackMin栈顶元素1
5. 5入栈 ， 5>此时的栈StackMin的栈顶元素1，不压入StackMin栈顶元素1

如图所示

代码实现

方法1

 public static void getMin1(int [] a){
        Stack<Integer> stack  = new Stack<>();
        Stack<Integer> stackMin  = new Stack<>();

        for (int i = 0; i <a.length ; i++) {
            stack.push(a[i]);
            if (stackMin.isEmpty()){
                stackMin.push(a[i]);
            }else if(stack.peek()<=stackMin.peek()){
                stackMin.push(a[i]);
            }
        }
        int size = stack.size();
        for (int i = 0; i <size ; i++) {
            if(stack.peek()<=stackMin.peek()){
                System.out.println(stackMin.pop());
                break;
            }
            stack.pop();
        }

    }

方法2

public static void getMin2(int [] a){
        Stack<Integer> stack  = new Stack<>();
        Stack<Integer> stackMin  = new Stack<>();

        for (int i = 0; i <a.length ; i++) {
            stack.push(a[i]);
            if (stackMin.isEmpty()){
                stackMin.push(a[i]);
            }else if(stack.peek()<=stackMin.peek()){
                stackMin.push(a[i]);
            }else {
                stackMin.push(stackMin.peek());
            }
        }
        int size = stack.size();
        for (int i = 0; i <size ; i++) {
            if(stack.peek()<=stackMin.peek()){
                System.out.println(stackMin.pop());
                break;
            }
            stack.pop();
        }

    }

二者方法区别

1.方法1 省空间，费时间
2.方法2 省时间，费空间