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

    包含min函数的栈

    题目

    牛客网

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

    解题思路

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