1. 队列

1.1 设计循环双端队列（641）

  • 双向链表

    1. class MyCircularDeque {
    2.   private int capacity;
    3.   private int size;
    4.   private Node head;
    5.   private Node tail;
    7.   public MyCircularDeque(int k) {
    8.       capacity = k;
    9.       size = 0;
    10.       head = new Node(-1, null, null);
    11.       tail = new Node(-2, head, null);
    12.       head.next = tail;
    13.   }
    15.   public boolean insertFront(int value) {
    16.       if ( size >= capacity ) {
    17.           return false;
    18.       }
    19.       size++;
    20.       Node temp = head.next;
    21.       head.next = new Node(value, head, temp);
    22.       temp.prev = head.next;
    23.       return true;
    24.   }
    26.   public boolean insertLast(int value) {
    27.       if ( size >= capacity ) {
    28.           return false;
    29.       }
    30.       size++;
    31.       Node last = tail.prev;
    32.       last.next = new Node(value, last, tail);
    33.       tail.prev = last.next;
    34.       return true;
    35.   }
    37.   public boolean deleteFront() {
    38.       if (size == 0) {
    39.           return false;
    40.       }
    41.       size--;
    43.       Node temp = head.next.next;
    44.       head.next = head.next.next;
    45.       temp.prev = head;
    46.       return true;
    47.   }
    49.   public boolean deleteLast() {
    50.       if (size == 0) {
    51.           return false;
    52.       }
    53.       size--;
    54.       Node temp = tail.prev.prev;
    55.       temp.next = temp.next.next;
    56.       tail.prev = temp;
    57.       return true;
    58.   }
    60.   public int getFront() {
    61.       if (size == 0) {
    62.           return -1;
    63.       }
    64.       Node temp = head.next;
    65.       return temp.value;
    67.   }
    69.   public int getRear() {
    70.       if (size == 0) {
    71.           return -1;
    72.       }
    73.       Node temp = tail.prev;
    74.       return temp.value;
    75.   }
    77.   public boolean isEmpty() {
    78.       return size == 0;
    79.   }
    81.   public boolean isFull() {
    82.       return size == capacity;
    83.   }
    85.   private static class Node {
    86.       int value;
    87.       Node prev;
    88.       Node next;
    90.       public Node(int value, Node prev, Node next) {
    91.           this.value = value;
    92.           this.prev = prev;
    93.           this.next = next;
    94.       }
    96.   }
    97. }

  • 数组： ```java

public class MyCircularDeque {

  1. // 1、不用设计成动态数组，使用静态数组即可
  2. // 2、设计 head 和 tail 指针变量
  3. // 3、head == tail 成立的时候表示队列为空
  4. // 4、tail + 1 == head 表示为满
  5. // 5、注意做减法指针可能变成负数 可以用 (tail - 1 + capacity ) % capacity 来做tail移位
  7. private final int capacity;
  8. private final int[] arr;
  9. private int head;
  10. private int tail;
  12. public MyCircularDeque(int k) {
  13.     // 多存一个用于区分队列满和空的情况
  14.     capacity = k + 1;
  15.     arr = new int[capacity];
  16.     head = 0;
  17.     tail = 0;
  18. }
  20. public boolean insertFront(int value) {
  21.     if (isFull()) {
  22.         return false;
  23.     }
  24.     head = (head - 1 + capacity) % capacity;
  25.     arr[head] = value;
  26.     return true;
  27. }
  29. public boolean insertLast(int value) {
  30.     if (isFull()) {
  31.         return false;
  32.     }
  33.     arr[tail] = value;
  34.     tail = (tail + 1) % capacity;
  35.     return true;
  36. }
  38. public boolean deleteFront() {
  39.     if (isEmpty()) {
  40.         return false;
  41.     }
  42.     // front 被设计在数组的开头，所以是 +1
  43.     head = (head + 1) % capacity;
  44.     return true;
  45. }
  47. public boolean deleteLast() {
  48.     if (isEmpty()) {
  49.         return false;
  50.     }
  51.     // rear 被设计在数组的末尾，所以是 -1
  52.     tail = (tail - 1 + capacity) % capacity;
  53.     return true;
  54. }
  56. public int getFront() {
  57.     if (isEmpty()) {
  58.         return -1;
  59.     }
  60.     return arr[head];
  61. }
  63. public int getRear() {
  64.     if (isEmpty()) {
  65.         return -1;
  66.     }
  67.     // 当 tail 为 0 时防止数组越界才加的capacity
  68.     return arr[(tail - 1 + capacity) % capacity];
  69. }
  71. public boolean isEmpty() {
  72.     return head == tail;
  73. }
  75. public boolean isFull() {
  76.     // 注意：这个设计是非常经典的做法
  77.     return (tail + 1) % capacity == head;
  78. }

}

  1. <a name="qF8oM"></a>
  2. ### 1.2 滑动窗口最大值（239）
  4. - 直接循环O(n^2)
  5. ```java
  6.     public int[] maxSlidingWindow(int[] nums, int k) {
  7.         int[] resultArr = new int[nums.length - k + 1];
  8.         for (int i = 0; i < nums.length - k + 1; i++) {
  9.             int max = nums[i];
  10.             for (int j = i; j < i + k; j++) {
  11.                 max = Math.max(max, nums[j]);
  12.             }
  13.             resultArr[i] = max;
  14.         }
  15.         return resultArr;
  16.     }

  • 借助队列

    1.3 层次遍历二叉树（102）

  • BFS即可

    2. 栈

    2.1 最小栈（155）

    1.   class MinStack {
    2.       Deque<Integer> stack;
    3.       Deque<Integer> minStack;
    5.       public MinStack() {
    6.           stack = new LinkedList<Integer>();
    7.           minStack = new LinkedList<Integer>();
    8.           minStack.push(Integer.MAX_VALUE);
    9.       }
    11.       public void push(int x) {
    12.           stack.push(x);
    13.           minStack.push(Math.min(minStack.peek(), x));
    14.       }
    16.       public void pop() {
    17.           stack.pop();
    18.           minStack.pop();
    19.       }
    21.       public int top() {
    22.           return stack.peek();
    23.       }
    25.       public int getMin() {
    26.           return minStack.peek();
    27.       }
    28.   }

    2.2 删除链表第N个元素

  • 解法一：栈，pop出 n+1个元素

    1.   public ListNode removeNthFromEnd(ListNode head, int n) {
    2.       ListNode dummyHead = new ListNode(0, head);
    3.       ListNode temp = dummyHead;
    4.       Stack<ListNode> stack = new Stack<>();
    5.       while (null != temp) {
    6.           stack.push(temp);
    7.           temp = temp.next;
    8.       }
    10.       ListNode prev = stack.pop();
    11.       for (int i = 0; i < n; i++) {
    12.           prev = stack.pop();
    13.       }
    14.       if (prev.next != null) {
    15.           prev.next = prev.next.next;
    16.       }
    18.       return dummyHead.next;
    19.   }

  • 解法二：双指指针，slow和fast间隔N个位置

    2.3 有效括号（20）

  • 解法一：用栈

    1.   public boolean isValid(String s) {
    2.       if (s.length() % 2 == 1) {
    3.           return false;
    4.       }
    5.       Map<Character, Character> map = new HashMap<>();
    6.       map.put('(', ')');
    7.       map.put('[', ']');
    8.       map.put('{', '}');
    10.       Stack<Character> stack = new Stack<>();
    12.       char[] charArr = s.toCharArray();
    13.       for (char c : charArr) {
    14.           if (map.containsKey(c)) {
    15.               stack.push(c);
    16.               continue;
    17.           }
    18.           if (stack.isEmpty()) {
    19.               return false;
    20.           }
    21.           Character temp = stack.pop();
    22.           if (!map.get(temp).equals(c)) {
    23.               return false;
    24.           }
    26.       }
    27.       return stack.isEmpty();
    28.   }

    2.4 接雨水（42）hard

  • 解法一：栈 ```java public int trap(int[] height) {

    1.   Deque<Integer> stack = new LinkedList<Integer>();
    2.   int result = 0;
    3.   for (int i = 0; i < height.length; ++i) {
    4.       while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
    5.           int top = stack.pop();
    6.           if (stack.isEmpty()) {
    7.               break;
    8.           }
    9.           int left = stack.peek();
    10.           int widthTemp = i - left - 1;
    11.           int heightTemp = Math.min(height[left], height[i]) - height[top];
    12.           result += widthTemp * heightTemp;
    13.       }
    14.       stack.push(i);
    15.   }
    16.   return result;

    }

```

  • 解法二：动态规划：见动态规划章节

    2.5 柱状图中最大的矩形（84）hard

  • 单调栈解决

单调栈关注一下
序号 题目 题解
42. 接雨水（困难） 暴力解法、优化、双指针、单调栈
739. 每日温度（中等） 暴力解法 + 单调栈
496. 下一个更大元素 I（简单） 暴力解法、单调栈
316. 去除重复字母（困难） 栈 + 哨兵技巧（Java、C++、Python）
901. 股票价格跨度（中等） 「力扣」第 901 题：股票价格跨度（单调栈）
402. 移掉K位数字
581. 最短无序连续子数组