• 包含min函数的栈
    • 题目
    • 解题思路

    包含min函数的栈

    题目

    牛客网

    定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的 min 函数(时间复杂度应为O(1))。

    解题思路

    1. 通过增加最小栈来记录当前最小节点
    1. private LinkedList<Integer> stack = new LinkedList<>();
    2. private LinkedList<Integer> min = new LinkedList<>();
    3. public void push(int node) {
    4. stack.addLast(node);
    5. if (min.isEmpty()) {
    6. min.addLast(node);
    7. return;
    8. }
    9. if (node < min.peekLast()) {
    10. min.addLast(node);
    11. } else {
    12. min.addLast(min.peekLast());
    13. }
    14. }
    15. public void pop() {
    16. if (stack.isEmpty()) {
    17. return;
    18. }
    19. stack.removeLast();
    20. min.removeLast();
    21. }
    22. public int top() {
    23. if (stack.peekLast() == null) {
    24. return 0;
    25. }
    26. return stack.peekLast();
    27. }
    28. public int min() {
    29. if (min.peekLast() == null) {
    30. return 0;
    31. }
    32. return min.peekLast();
    33. }