单调栈

主要解决寻找单向数组某元素前后值大于该元素的值

class MonotonousStack {
  final static int N = 10010;
  
  public static void move(int[]	q) {
    int[] stk = new int[N];
    int size = -1;
    
    for (int i = 0; i < q.length; i++) {
      // 判断栈内元素是否满足单调性
      while (size >= 0 && stk[size] > q[i]) size--;
      if (size >= 0) System.out.print(stk[size] + " ");
      else System.out.print(-1 + " ");
      stk[size++] = q[i];
    }
  }
}

单调队列

主要解决滑动窗口问题

class MonotonousQueue {
  final static int N = 10010;
  
  public static void move(int[] a, int k) {
    int[] q = new int[N];
    int hh = 0, tt = -1;
    for (int i = 0; i < q.length; i++) {
      // 区间头部元素出队
      if (hh <= tt && i - k + 1 > q[hh]) hh ++;
      // 检查队尾元素是否满足单调性
      while (hh <= tt && a[q[tt]] >= a[i]) tt--;
      // 将元素下标添加至队列
      q[++tt] = i;
      // 输出队列头部元素
      if (i + 1 >= k) System.out.print(a[q[hh]] + " ");
    }
  }
}

KMP

class KMP {
  final static int N = 10010;
  
  public static void match(String target, String match) {
    int m = targte.length(), n = match.length();
    char[] s = new char[m + 1], p = new char[n + 1];
    int[] next = new int[N];
    
    System.arraycopy(target.toCharArray(), 0, s, 1, m);
    System.arraycopy(match.toCharArray(), 0, p, 1, n);
    
    // next 数组构造
    for (int i = 2, j = 0; i <= n; i++) {
      while (j != 0 && q[i] != q[j + 1]) j = next[j];
      if (q[i] == q[j + 1]) j++;
      next[i] = j;
    }
    
    // 开始匹配
    for (int i = 1, j = 0; i <= m; i++) {
      while (j != 0 && s[i] != q[j + 1]) j = next[j];
      if (s[i] == q[j + 1]) j++;
      if (j == n) {
        System.out.print(i - n + " ");
        j = next[j];
      }
    }
  }
}

• 参考来源
  • ACWing - 算法基础课