包含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. }