题目描述

题解

栈

这道题实现的是栈结构, 所以肯定需要一个栈提供基础的功能, 难点在于如何实现一般栈结构无法存在的min功能.

本来想通过堆结构来保存当前的最小值, 但是时间复杂度不够友好, 所以换一个思路, 用另外一个栈作为辅助, 从而实现min功能.

大致思路就是, 当实现添加元素的功能时, 除了正常往栈1中添加元素外, 还要考虑是否往栈2中添加. 往栈2中添加元素的条件为是否<=栈1的栈顶元素, 把更小的元素压入栈2, 就能时刻保证栈2中的元素是排过序的, 栈2的栈顶元素一定为栈1中的最小元素.

如果执行了min方法, 那么把栈2的栈顶元素输出即可

十分重要的一点在于, 如果执行了pop方法, 将栈1的栈顶元素弹出的同时, 还要查看栈2的栈顶元素是否与栈1的栈顶元素相等.如果相等, 栈2也需要把栈顶元素弹出.

class MinStack {

    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;

    /**
         * initialize your data structure here.
         */
    public MinStack() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    public void push(int x) {
        stack1.addLast(x);

        if (stack2.isEmpty()) {
            stack2.addLast(x);
        } else if (x <= stack2.getLast()) {
            stack2.addLast(x);
        }
    }

    public void pop() {
        if (!stack2.isEmpty() && stack1.getLast().equals(stack2.getLast())) {
            stack2.pollLast();
        }
        stack1.pollLast();

    }

    public int top() {
        return stack1.getLast();
    }

    public int min() {
        return stack2.getLast();
    }
}