LeetCode——最小栈

NO.155 最小栈简单

思路一：两个栈 利用栈去实现栈，看起来好像比较奇怪，但这道题的重点是在于如何每次 O(1) 时间获取到最小值。本题不需要考虑栈空。

用一个栈 min 存放最小元素，当有新元素 x 入栈的时候，判断 x 是否小于等于 min 的栈顶元素，true 将 x 推入 min，否则只推入主栈。弹出元素时，判断弹出的元素 y ，是否等于 min 的栈顶元素，true 将 min 的栈顶元素也一起弹出，否则只弹出主栈元素。

public class MinStack {
    Stack<Integer> stack;
    Stack<Integer> min;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (!min.isEmpty()) {
            if (x <= min.peek()) {
                min.push(x);
            }
        } else {
            min.push(x);
        }
    }

    public void pop() {
        int pop = stack.pop();
        if (pop == min.peek()) {
            min.pop();
        }
    }

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

    public int getMin() {
        return min.peek();
    }
}

思路二：一个栈 使用一个栈存储数据，用一个变量 min 保存最小的元素，当新入栈元素 x 小于等于 min 的时候，先将 min 入栈且更新 min 为 x，再将 x 入栈，保持栈中当前最小元素 min 的下面”压着”下一个最小元素。

出栈时，如果出栈元素 y 等于 min，则 y 出栈后，再出栈一个元素作为 min。

public class MinStack {
    Stack<Integer> stack;
    int min;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        stack = new Stack<>();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        if (x <= min) {
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {
        Integer pop = stack.pop();
        if (pop == min) {
            min = stack.pop();
        }
    }

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

    public int getMin() {
        return min;
    }
}

思路三：不使用栈 用一个链表实现栈，链表节点有一个 min 保存当前节点插入时栈内的最小值。

class Node {
    int value;
    int min;
    Node next;

    public Node(int value, int min) {
        this.min = min;
        this.value = value;
        this.next = null;
    }
}

每次新元素入栈时，采用头插法，新节点的 min 保存当前栈内的最小元素，head 指针始终指向栈顶(表头)：

public class MinStack {
    Node head;

    /**
     * initialize your data structure here.
     */
    public MinStack() {

    }

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

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

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

    public int getMin() {
        return head.min;
    }
}

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.155 最小栈 简单

NO.155 最小栈简单