算法学习_最小栈

最小栈

题目

lettcode-155题
难度：简单

解题思路

题目基本上就是要求找出一个栈中最小的值，通过java中内置的栈的方法即可实现这一目标

首先我的想法是通过遍历比较所有的值来找出最小的那个值，但是这样子消耗了较多的时间，而且题目希望是设计一种栈的结构，而不是直接用栈的方法。

所以后面换了一种新的方法，就是使用链表来实现，这样子的效率是较高的，相比于之前的方法，用时整整少了200多毫秒

具体实现方式如下

具体代码(第一种思路)

class MinStack {

    Stack<Integer> stack;
    public MinStack() {
        stack = new Stack<Integer>();
    }

    public void push(int val) {
        stack.push(val);
    }

    public void pop() {
        stack.pop();
    }

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

    public int getMin() {
        int min=stack.get(0);;
        for (int i=0;i<stack.size();i++){
            if (stack.get(i)<min){
                min=stack.get(i);
            }
        }
        return min;
    }
}

具体代码(第二种思路)

class MinStack {

    private Node head;
    
    public void push(int x) {
        if(head == null) 
            head = new Node(x, x);
        else 
            head = new Node(x, Math.min(x, head.min), head);
    }

    public void pop() {
        head = head.next;
    }

    public int top() {
        return head.val;
    }

    public int getMin() {
        return head.min;
    }
    
    private class Node {
        int val;
        int min;
        Node next;
        
        private Node(int val, int min) {
            this(val, min, null);
        }
        
        private Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}