算法模板整理

算法模板整理

二分查找

算法分析

有单调性一定可以二分，但是不一定非要有单调性才能二分。本质：将区间一分为二，一半满足需求，另一边不满足，则二分可以找到边界。

模板1

public int search(int[] nums, int left, int right, int target) {
    while (left < right) {
        // 选择中位数时下取整
        int mid = left + (right - left) / 2;
        if (check(mid)) {
            // 下一轮搜索区间是 [left, mid]
            right = mid
        } else {
            // 下一轮搜索区间是 [mid + 1, right]
            left = mid + 1
        }
    }
}

模板2

public int search(int[] nums, int left, int right, int target) {
    while (left < right) {
        // 选择中位数时上取整
        int mid = left + (right - left + 1) / 2;
        if (check(mid)) {
            // 下一轮搜索区间是 [mid, right]
            left = mid;
        } else {
            // 下一轮搜索区间是 [left, mid - 1]
            right = mid - 1;
        }
    }
}

分析

(left + right) / 2 等价于 left + right >> 2，等价于left + (right - left) / 2，最后一个防止整数溢出，但做题很少考虑。

当采用 left = mid，right = mid - 1 这种更新方式时，中位数 mid 需要向上取整，否则会导致边界问题。和快速排序的更新边界类似。

当right = left + 1，mid = (left + right) / 2 = left，更新left = mid的时候left的值没变，所以会导致死循环。

模板1和模板2的区别：
模板1是在满足check()的区间内找到左边界，模板2在满足check()的区间内找到右边界。在不存在满足check的区间时（如数组中没有所求元素），模板1找到lower_bound，也就是大于所求元素的第一个数，模板二找到upper_bound，也就是小于所求元素的第一个数。具体想的时候可以举例模拟，来判断用哪个模板。
模板的记忆方法：
mid向下取整，对应left = mid + 1，mid向上取整，对应left = mid。判断mid满足check，更新的 lo 或 hi 就一定要包含mid。
例题：
https://www.acwing.com/problem/content/791/

找三次方根（浮点数二分）

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double n = sc.nextDouble(); // −10000 ≤ n ≤ 10000
        double lo = -10000, hi = 10000;
        // 题目要求保留6位小数，根据经验值精确到10e-8
        while (hi - lo > 1e-8) {
            double mid = (lo + hi) / 2;
            if (Math.pow(mid, 3) >= n) hi = mid;
            else lo = mid;
        }
        System.out.format("%.6f", lo);
    }
}

由于是浮点数二分，不用考虑数组边界情况，更新lo和hi都不需要缩小范围。记忆：题目要求保留n位小数，根据经验值需要精确到小数点后n+2位。 Java的format，double用%f，而不是%lf。

快速排序

算法分析

确定切分点（q[lo], q[hi], q[lo + hi >> 2], q[random]）都可以。
调整切分点的位置（算法核心）
递归处理切分点左右两段。（先操作，后递归，而归并排序刚好相反）

不稳定的排序，如果将待排数组的元素改成一个双关键字的数据结构，保证每个元素都不同，就能让它稳定。
平均O(logn)，最坏O(n^2)

模板

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    private static int[] q;
    private static int n;
    public static void main(String[] args) throws IOException {
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(in);
        n = Integer.parseInt(br.readLine());
        q = new int[n];
        String[] res = br.readLine().split(" ");
        for (int i = 0; i < n; i++) q[i] = Integer.parseInt(res[i]);
        quick_sort(q, 0, n - 1);
        for (int i = 0; i < n; i++) System.out.format("%d ", q[i]);
        br.close();
    }
    public static void quick_sort(int[] q, int lo, int hi) {
        if (lo >= hi) return; // lo是有可能到hi右侧的（区间内没有数），所以不能写 == 
        int i = lo - 1, j = hi + 1;
        // 1. 确定切分点
        int v = q[lo + (hi - lo) / 2]; // 切分元素选择q[mid]（多种选法之一）
        // 2. 调整切分点位置，保证 i 左侧的元素 <= v，保证 j 右侧的元素 >= v
        while (i < j) {
            while (q[++i] < v); 
            while (q[--j] > v);
            if (i < j) exch(q, i, j);
        }
        // 3. 递归处理切分点左右两段。
        quick_sort(q, lo, j);
        quick_sort(q, j + 1, hi); 
        // 注意：偏向右侧更新边界时，不能选择最右侧元素q[hi]做切分值，否则可能出现边界问题。
        // 同理，更新节点也可以 quick_sort(q, lo, i - 1); quick_sort(q, i, hi); 这样就是偏向左侧更新边界，不能选q[lo]做切分值（边界问题和二分搜索时相同）
    }
    public static void exch(int[] q, int i, int j) {
        int temp = q[i];
        q[i] = q[j];
        q[j] = temp;
    }
}

代码分析

刷Leetcode很难接触到需要手动写输入输出，注意一下最好不要用Scanner而是使用BufferReader读取数据。
这个模板和在《Algorithms 4》里面的不太相同，是带着切分点进行交换操作，递归调用时也要覆盖到所有数据。
和二分相同，注意边界问题。更新时偏左([lo, i - 1], [i, hi])则不能拿左侧端点当切分点，更新时偏右([lo, j], [j + 1, hi])则不能拿右侧端点当切分点。
快速选择模板（第k个元素）
```java import java.io.IOException; import java.util.Scanner;

public class Main {

private static int[] q;
private static int n;
private static int k;
public static void main(String[] args) throws IOException {
    Scanner scanner = new Scanner(System.in);
    n = scanner.nextInt();
    k = scanner.nextInt();
    q = new int[n];
    for (int i = 0; i < n; i++) {
        q[i] = scanner.nextInt();
    }
    int result = quick_find(0, n - 1, k);
    System.out.println(result);
}
public static int quick_find(int lo, int hi, int k) {
    // 思路：使用快排的找partitioning point的思想，找到一个切分点p后，如果左侧长度Sl >= k，在左侧找第k个
    // 如果左侧长度Sl < k，在右侧找第(k - Sl)个。
    if (lo == hi) {
        return q[lo];
    }
    int i = lo - 1, j = hi + 1;
    int p = q[i + j >> 1];
    while (i < j) {
        while (q[ ++ i] < p);
        while (q[ -- j] > p);
        if (i < j) {
            int temp = q[i];
            q[i] = q[j];
            q[j] = temp;
        }
    }
    int sl = j - lo + 1;
    if (k <= sl) {
        return quick_find(lo, j, k);
    }
    return quick_find(j + 1, hi, k - sl);
}

}

> 注意这里一定是[lo, j], [j + 1, hi]，为了匹配k的个数

<a name="5wc4W"></a>
## 归并排序
<a name="2YG3P"></a>
### 算法分析

1. 选择划分点 mid = lo + hi >> 1
1. 递归被划分的 left 和 right 进行操作
1. 归并，将 left 和 right部分合并为一个数组（核心）

**稳定的排序**，前提是merge的时候，当left，right两数组出现相同值的时候，选择left中的元素（在原数组中位置靠前）。<br />**平均，最坏O(logn)**
<a name="RfWCV"></a>
### 模板
```java
public static void merge_sort(int[] q, int lo, int hi)
{
    if (lo >= hi) 
    {
        return;
    }
    // 1. 选择划分点
    int mid = lo + hi >> 1;
    // 2. 分别对左右两段进行递归操作
    merge_sort(q, lo, mid);
    merge_sort(q, mid + 1, hi);
    // 3. 归并左右两段
    int k = 0, i = lo, j = mid + 1;
    while (i <= mid && j <= hi) 
    {
        if (q[i] <= q[j])
        {
            aux[k ++ ] = q[i ++ ];
        }
        else 
        {
            aux[k ++ ] = q[j ++ ];
        }
    }
    while (i <= mid)
    {
        aux[k ++ ] = q[i ++ ];
    }
    while (j <= hi)
    {
        aux[k ++ ] = q[j ++ ];
    }
    for (i = lo, k = 0; i <= hi; i ++ , k ++ )
    {
        q[i] = aux[k];
    }
}

省略了main()，注意aux[]要在merge_sort()外部初始化。

找逆序对

import java.util.Scanner;

public class Main {
    private static int[] q;
    private static int n;
    private static int[] temp;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        q = new int[n];
        temp = new int[n];
        // 用于merge sort的辅助数组

        for (int i = 0; i < n; i++) {
            q[i] = scanner.nextInt();
            temp[i] = q[i];
        }
        // 思路：按照归并排序的思路，将数组递归的分为两部分，此时逆序对的总数量 = 左侧逆序对数量 + 右侧逆序对数量 + 跨边逆序对数量
        // 左右侧都最终被转化为跨边，跨边的计算方式为：在merge操作时，前进右侧指针j时，将result += 左侧指针i到mid的长度(mid - i + 1)
        long result = 0; // max value = n(n - 1) / 2     n ~ [0, 10^5] 超出Integer.MAX_VALUE=65535，所以要用long
        result = merge_count(0, n - 1);
        System.out.println(result);
    }

    private static long merge_count(int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = lo + hi >> 1;
        int i = lo, j = mid + 1, k = 0;
        // 1. 左侧逆序对数量 + 右侧逆序对数量
        long result = merge_count(lo, mid) + merge_count(mid + 1, hi);
        // 2. 跨边逆序对数量
        while (i <= mid && j <= hi) {
            if (q[i] <= q[j]) temp[k ++ ] = q[i ++ ];
            else {
                temp[k ++ ] = q[j ++ ];
                result += mid - i + 1;
            }
        }
        while (i <= mid) temp[k ++ ] = q[i ++ ];
        while (j <= hi) temp[k ++ ] = q[j ++ ];
        for (k = 0, i = lo; i <= hi; k ++ , i ++ ) q[i] = temp[k];
        return result;
    }
}

高精度

高精度加法

//
// Created by jushen on 2021/2/23.
//
#include <iostream>
#include <vector>
using namespace std;

// 使用引用避免对象复制
vector<int> add(vector<int> &A, vector<int> &B)
{
    // 保证A是较长的一个大数，避免一些判断
    if (A.size() < B.size()) add(B, A);
    int num = 0;
    vector<int> C;
    for (int i = 0; i < A.size(); i ++ )
    {
        num += A[i];
        if (i < B.size()) num += B[i];
        C.push_back(num % 10);
        num /= 10;
    }
    if (num) C.push_back(num);
    return C;
}

int main()
{
    vector<int> A, B;
    string AString, BString;
    cin >> AString >> BString; // 注意用scanf需要实现分配空间,如下所示
    // 倒序插入，方便进位
    for (int i = AString.size() - 1; i >= 0; i -- ) A.push_back(AString[i] - '0');
    for (int i = BString.size() - 1; i >= 0; i -- ) B.push_back(BString[i] - '0');
    vector<int> C = add(A, B);
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;
    return 0;
}

如果数组按照正常的顺序高位在前添加元素，当最高位需要进位时，需要让数组做整体移动。
让低位先插入数组，高位在数组末尾，进位也只需要在尾部添加元素。
C++读入string类型就用cin吧，用scanf方法提交会报错。

高精度减法

//
// Created by jushen on 2021/2/23.
//
#include <iostream>
#include <vector>
using namespace std;

// A, B代表的数字比较大小
bool compare(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        if (A[i] != B[i]) return A[i] > B[i];
    }
    return true; // A = B，结果不加 -
}

vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int num = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        num = A[i] - num; // 减去借位
        if (i < B.size()) num -= B[i];
        C.push_back((num + 10) % 10); // 兼容num < 0
        if (num < 0) num = 1; // 设置借位
        else num = 0;
    }
    // 去除最高位前的0，但当计算结果为0时至少留一个0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    vector<int> A, B;
    string a, b;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    vector<int> C;
    // A - B = - (B - A)  当 A - B < 0时表示成右边
    if (compare(A, B)) C = sub(A, B);
    else
    {
        cout << "-";
        C = sub(B, A);
    }
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    return 0;
}

为了让两个大数的低位对齐，也逆向存储到数组中。
注意代码中对 A - B < 0 情况的处理。
需要去除最高位前的0。

高精度乘法

//
// Created by jushen on 2021/2/23.
//
#include <iostream>
#include <vector>
using namespace std;

// 使用引用避免对象复制
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int num = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        num += A[i] * b;
        C.push_back(num % 10);
        num /= 10;
    }
    if (num) C.push_back(num);
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    vector<int> A;
    string AString;
    int b;
    cin >> AString >> b;
    for (int i = AString.size() - 1; i >= 0; i -- ) A.push_back(AString[i] - '0');
    vector<int> C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl;
    return 0;
}

和加法类似。注意是大数A x 小数b。

高精度乘法

//
// Created by jushen on 2021/2/23.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    int num = 0;
    // 从高位开始计算（和前面三个模板都不同）
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        num = num * 10 + A[i];
        C.push_back(num / b);
        num %= b;
    }
    r = num;
    reverse(C.begin(), C.end()); // 为了方便去除高位前的0，翻转数组
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main()
{
    vector<int> A;
    string a;
    int b, r = 0;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    vector<int> C = div(A, b, r);
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl << r;
    return 0;
}

为了返回r，传引用。
除法是从高位开始算，也不存在低位对齐的问题，但为了好记，还是反向存储，只是在做除法运算的时候要记得从高位（末尾）开始。
同样需要去除最高位前的0，去除之前要将翻转数组，避免去除头部元素导致数组整体移动。

前缀和与差分

一维数组前缀和

//
// Created by jushen on 2021/2/23.
//

#include <iostream>
using namespace std;

const int N = 100010;

int main()
{
    int a[N], S[N];
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        S[i] = S[i - 1] + a[i];
    }
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", S[r] - S[l - 1]);
    }
    return 0;
}

S[i] = S[i - 1] + a[i] a[left] + … + a[right] = S[right] - S[left - 1]

二维数组前缀和

//
// Created by jushen on 2021/2/22.
//
#include <iostream>
using namespace std;

const int N = 1010; // size of array
int S[N][N]; // S[i][i] = Sum of elements in i*i matrix(q[1][1] ~ q[i][i])

int main()
{
    int n, m, times;
    scanf("%d%d%d", &n, &m, &times);
    // Initialize q, S (q can be removed)
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            scanf("%d", &S[i][j]);
            S[i][j] += S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1];
        }
    }
    while (times -- )
    {
        int x1, x2, y1, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        // Sum of elements in the matrix
        printf("%d\n", S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]);
    }
    return 0;
}

S[i, j] = 第i行j列格子左上部分所有元素的和 S[i, j] += S[i - 1, j] + S[i, j - 1] - S[i - 1, j - 1] + a[i, j]; 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为： S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

一维数组差分

差分：给出S数组，求a数组，和前缀和是逆运算。差分的价值在于：能够让一个区间内的所有元素 + - 的操作由O(n) -> O(1)

//
// Created by jushen on 2021/2/22.
//
#include <iostream>
using namespace std;

const int N = 100010;
int S[N], a[N]; // S is the prefixSum array of a ----- a is the difference array of S

// Elements in S[lo]~S[hi] add value ----- a[lo] += value, a[hi + 1] -= value
void insert(int lo, int hi, int value)
{
    a[lo] += value;
    a[hi + 1] -= value;
}

int main()
{
    int n, times;
    scanf("%d%d", &n, &times);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &S[i]);
        insert(i, i, S[i]); // Initialize a[] by insert()
    }
    while (times -- )
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c); // update a[]

    }
    // Update and output S[] by updated a[]
    for (int i = 1; i <= n; i ++ )
    {
        S[i] = S[i - 1] + a[i];
        printf("%d ", S[i]);
    }
    return 0;
}

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c 初始化a数组也可以利用以上公式。

二维数组差分

//
// Created by jushen on 2021/2/22.
//
#include <iostream>
using namespace std;

const int N = 1010;
int S[N][N], a[N][N];

void insert(int x1, int y1, int x2, int y2, int value)
{
    // 需要注意的是，每次更新a[i][j]，都会影响到S[i][j]所在行列及其右下方的所有元素
    // 只影响S[x1][y1] ~ S[x2][y2]则需要额外的操作恢复多余的影响，如下所示
    a[x1][y1] += value; // update S[i][j] (x1 <= i <= n, y1 <= j <= m)
    // remove other changes
    a[x2 + 1][y1] -= value;
    a[x1][y2 + 1] -= value;
    a[x2 + 1][y2 + 1] += value;
}

int main()
{
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            scanf("%d", &S[i][j]);
            insert(i, j, i, j, S[i][j]); // Initialize a[][] by insert()
        }
    }
    while (q -- )
    {
        int x1, x2, y1, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + a[i][j];
            printf("%d ", S[i][j]);
        }
        printf("\n");
    }
}

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c： S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

双指针

找指针移动的单调性（慢指针不走回头路）。比如两个一起往后走，或者一前一后。将O(n^2)问题转化为O(n)，即两个指针各遍历一次数组。

最长连续不重复子序列

//
// Created by jushen on 2021/2/24.
//
#include <iostream>
using namespace std;

const int N = 100010;
int arr[N], S[N]; // arr保存原数组，S类似hashmap，用于快速判断数字出现次数，S[100] = 1 --- 100出现一次
// 数组要在main外部初始化，否则数组内是魔法值

int main()
{
    int n = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &arr[i]);
    int maxLen = 0;
    for (int i = 0, j = 0; i < n; i ++ )
    {
        S[arr[i]] ++ ;
        while (i > j && S[arr[i]] > 1)
            S[arr[j ++ ]] -- ;
        maxLen = max(maxLen, i - j + 1);
    }
    printf("%d", maxLen);
    return 0;
}

这题的单调性思考：如果当前j~i内有重复，那么j往回走也一定会有重复，所以j只需要往前走。

数组元素的目标和

//
// Created by 15813 on 2021/2/26.
//
#include <iostream>
using namespace std;

const int N = 100010;
int a[N], b[N];

int main()
{
    int aLen, bLen, target;
    cin >> aLen >> bLen >> target;
    for (int i = 0; i < aLen; i ++ ) cin >> a[i];
    for (int i = 0; i < bLen; i ++ ) cin >> b[i];
    // 思路：双指针算法O(m + n)。找出单调性后，i在a上从左到右移动，j在b上从右到左移动
    int i = 0, j = bLen - 1, sum = 0;
    for (; i < aLen; i ++ )
    {
        sum = a[i] + b[j];
        while (j > 0 && sum > target) sum = a[i] + b[ -- j];
        if (sum == target) break;
    }
    cout << i << " " << j << endl;
    return 0;
}

单调性分析：一个指针向后，另一个指针想维持sum的大小就要向前，所以将指针初始化在数组两端，这样sum是偏大还是偏小都有唯一的方式更新指针。感觉很像一题在有序的二维矩阵中找数字，将指针初始化在左下角或右上角，思想一样。

位运算

num & (-num) = num的二进制表示中最低位1代表的大小。
求出num中1的个数：num循环减去num & (-num)，直到为0，记录减了几次。

单调队列和单调栈

queue内只存储当前队列中可能的最大值。如果新加入的数字的值大于queue中的的元素，则在插入queue之前需要去掉那些比它小的数字，在任意时刻滑动窗口中的最大值就是单调queue中的head元素。

滑动窗口的最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MonotonicQueue queue = new MonotonicQueue();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            queue.add(nums[i]);
            // 当滑动窗口内有k个值，才开始计算
            if (i >= k - 1) {
                ans.add(queue.max());
                // 当滑动窗口将要退出的元素是最大值，就需要手动将max从单调队列中移除，
                // 否则不影响结果，不需要要移除
                if (queue.max() == nums[i - k + 1]) queue.pop();
            }
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); ++i) res[i] = ans.get(i);
        return res;
    }

    // 实现单调队列Monotonic Queue的基本操作
    class MonotonicQueue {
        private Deque<Integer> deque = new LinkedList<>();
        public void add(int e) {
            // 删除不可能为最大值的元素
            while (!deque.isEmpty() && e > deque.peekLast()){
                deque.pollLast();
            }
            deque.offerLast(e);
        }
        public void pop() {
            deque.pollFirst();
        }
        public int max() {
            return deque.getFirst();
        }
    }

}

队列总是单调递减，每当一个新元素入队时，都会向队头head突进并击飞路径上所有比它小的元素，让它们出队。自己停在合适的位置，使队列保持单调递减。本题维护这样一个单调队列就能保证每时每刻都知道滑动窗口中的最大值，即使当前最大值被滑到了窗口外，也能从队列中找到下一个最大值。

下一个更大元素Ⅰ

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> deque = new LinkedList<>();
        Map<Integer, Integer> map = new HashMap<>();
        int[] res = new int[nums1.length];
        // 维护单调栈的同时，记录题目要求的元素对<x, num2中第一个比x大的元素>
        // 由于num2中的数字互不相同，使用map存储。<x, 第一个比x大的元素>
        for (int num: nums2) {
            while (!deque.isEmpty() && num > deque.peekLast()) {
                map.put(deque.peekLast(), num);
                deque.pollLast();
            }
            deque.offerLast(num);
        }
        // 剩下的都是没有匹配的
        while (!deque.isEmpty()) {
            map.put(deque.pollLast(), -1);
        }
        for (int i = 0; i < res.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}

栈内就相当于一个金字塔形，每当要入栈一个元素，它就会从栈顶开始比它小的元素压碎（其他元素出栈），直到找到合适的位置入栈，从而保持金字塔。
在num压碎其他元素的时候，num就是这些元素在nums2中的下一个更大元素，将这个关系保存在map中即可（每个元素不重复）。

并查集

模板

class UnionFind {
    int count; // 不同集合的数量，初始化为节点个数（如果题目需要）
    int[] size; // 记录根节点n所在集合的节点数量，只有根节点的size才有意义。（如果题目需要）
    int[] parent; // 初始化parent[i] = i，每个节点都是根节点
    int[] rank; // rank[n]：节点n到叶节点的高度，用于按秩合并

    // 这里是传入一个二维数组，正常来讲传入n作为集合大小就好
    public UnionFind(char[][] grid) {
        count = 0;
        int m = grid.length;
        int n = grid[0].length;
        parent = new int[m * n];
        rank = new int[m * n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    parent[i * n + j] = i * n + j;
                    ++count;
                }
                rank[i * n + j] = 0;
            }
        }
    }

    public int find(int i) {
        // 返回根节点的同时，做路径压缩
        if (parent[i] != i) parent[i] = find(parent[i]);
        return parent[i];
    }

    public void union(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        // 如果已经在同一集合，就不用做任何操作
        if (rootx != rooty) {
            // 按秩合并，只有当两节点rank相等时，一个作为另一个的parent才会使rank++
            if (rank[rootx] > rank[rooty]) {
                parent[rooty] = rootx;
                // size[rootx] += size[rooty];
            } else if (rank[rootx] < rank[rooty]) {
                parent[rootx] = rooty;
                // size[rooty] += size[rootx];
            } else {
                parent[rooty] = rootx;
                // size[rootx] += size[rooty];
                rank[rootx] += 1;
            }
            --count;
        }
    }

    public int getCount() {
        return count;
    }
}

堆

是完全二叉树，最后一行从左到右依次排布，前面的行都是满的。小根堆，大根堆。
存储：一维数组，下标x的左节点2x，右节点2x+1。x从1开始。
核心操作：up(x), down(x)，拿小根堆举例：up(x)就是将一个元素上浮，不断和其父节点比较大小，若比父节点小则交换。
down(x)就是将父节点下移，与较小的子节点交换。

插入一个元素，先插到最后，再up(x)。删除一个元素，在用最后一个元素替换后，down(k)。修改一个元素，当修改的值大于原本的值，就down(x)，小于原本的值，就up(x)，否则不动。这里无脑down(x) + up(x)也是同一个效果。

第k个元素 + up, down模板

class Solution {
    private int[] heap;
    private int size;
    public int findKthLargest(int[] nums, int k) {
        if (k > nums.length) return Integer.MIN_VALUE;
        // heap: heap[1] ~ heap[size]
        heap = new int[nums.length + 1];
        size = nums.length;
        for (int i = 0; i < nums.length; ++ i) heap[i + 1] = nums[i];
        // 1. 建大根堆
        for (int i = size / 2; i > 0; -- i) down(i);
        // 2. 第k个元素->第k个堆顶->删去k-1个堆顶后的栈顶
        for (int i = 0; i < k - 1; ++ i) {
            // 将最后一个元素覆盖栈顶，size --。相当于栈顶被交换到最后然后舍弃。
            heap[1] = heap[size -- ];
            // 被交换到栈顶的元素下滤
            down(1);
        }
        return heap[1];
    }

    private void down(int n) {
        // 找到n节点和其左右子树的最小值下标
        int maxIndex = n;
        if (n * 2 <= size && heap[n * 2] > heap[n]) maxIndex = n * 2;
        if (n * 2 + 1 <= size && heap[n * 2 + 1] > heap[maxIndex]) maxIndex = n * 2 + 1;
        if (maxIndex != n) {
            swap(heap, n, maxIndex);
            down(maxIndex);
        }
    }

    private void up(int n) {
        while (n / 2 > 0 && heap[n / 2] < heap[n]) {
            swap(heap, n / 2, n);
            n /= 2;
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }   
}

快速选择的做法在：Kth题解

哈希表

hash函数：将大范围的数(-10^9 ~ 10^9)的数映射到10^5空间内。例如 x % 10^5。

哈希冲突：不同的数映射到同一个下标。

解决方式1：开放寻址法。

解决方式2：拉链法。

DFS, BFS

DFS：栈stack，空间复杂度O(h)，不能得到最短路。
BFS：队列queue，空间复杂度算法基础（一） - 图3

，有最短路的性质（搜到的第一个叶节点的路径即为最短路）。

层序遍历二叉树

https://leetcode.com/problems/binary-tree-level-order-traversal/submissions/

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
   List<List<Integer>> result = new ArrayList<>();
   if (root == null) return result;
   Deque<TreeNode> queue = new LinkedList<>();
   queue.offerLast(root);
   while (!queue.isEmpty()) {
       List<Integer> layer = new ArrayList<>();
       int nodeNum = queue.size();
       for (int i = 0; i < nodeNum; ++ i) {
           TreeNode cur = queue.pollFirst();
           layer.add(cur.val);
           if (cur.left != null) queue.offerLast(cur.left);
           if (cur.right != null) queue.offerLast(cur.right);
       }
       result.add(layer);
   }
   return result;
}
}

保存每一层的节点个数为nodeNum。

全排列（DFS回溯）

class Solution {

    private boolean[] used; // used[i]=当前路径上nums[i]是否被使用
    private List<Integer> path;
    private List<List<Integer>> result;

    public List<List<Integer>> permute(int[] nums) {
        path = new ArrayList<>();
        result = new ArrayList<>();
        used = new boolean[nums.length]; // 默认初始化为全false
        // DFS 回溯法
        dfs(nums, 0);
        return result;
    }

    private void dfs(int[] nums, int depth) {
        if (depth == nums.length) {
            result.add(new ArrayList(path)); // 注意要拷贝一个List，否则result内的path永远指向同一对象
            return;
        }
        for (int i = 0; i < nums.length; ++ i) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                dfs(nums, depth + 1);
                // 恢复现场，used[i]和path
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}

N皇后

class Solution {
    private List<List<String>> results;
    private List<Integer> result;
    private boolean[] col, dg, adg; // 当前列，对角线和反对角线的被占用状态

    public List<List<String>> solveNQueens(int n) {
        result = new ArrayList<>();
        results = new ArrayList<>();
        col = new boolean[n];
        dg = new boolean[2 * n - 1]; // 对角线个数为2n-1
        adg = new boolean[2 * n - 1];
        dfs(0, n);
        return results;
    }

    private void dfs(int row, int n) {
        if (row == n) {
            results.add(intListToStringList(result, n));
            return;
        }
        for (int i = 0; i < n; ++ i) {
            // dg: i = -row + b -> b = i + row  adg: i = row + b -> b = i - row 偏移量n - 1，使取值为[0:2n-2]。
            if (!col[i] && !dg[i + row] && !adg[row - i + n - 1]) {
                result.add(i);
                col[i] = dg[i + row] = adg[row - i + n - 1] = true;
                dfs(row + 1, n);
                col[i] = dg[i + row] = adg[row - i + n - 1] = false;
                result.remove(result.size() - 1);
            }
        }
    }

    private List<String> intListToStringList(List<Integer> list, int n) {
        List<String> stringList = new ArrayList<>();
        for (int pos: list) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[pos] = 'Q';
            stringList.add(new String(row));
        }
        return stringList;
    }
}

代码结构和全排列几乎相同，就是if剪枝操作有所不同。N皇后问题需要考虑列以及两条对角线，才能判断是否能放置。对角线分为正对角线和反对角线(anti-diagonal)

正对角线：y = -x + b b = x + y，所以board[row, col]所在的对角线编号为row + col，范围[0, 2n - 2]，映射到dg[2n - 1]中。
综上，board[row, col]所在的对角线为dg[row + col]。
反对角线：y = x + b b = y - x，所以board[row, col]所在的反对角线编号为row - col，范围为[-n + 1, n - 1]，为了映射到adg[2n - 1]中，增加偏移量n - 1。
综上，board[row, col]所在的反对角线为adg[row - col + n - 1]。

算法基础（一）

算法模板整理

二分查找

算法分析

模板1

模板2

分析

找三次方根（浮点数二分）

快速排序

算法分析

模板

代码分析

快速选择模板（第k个元素）

找逆序对

高精度

高精度加法

高精度减法

高精度乘法

高精度乘法

前缀和与差分

一维数组前缀和

二维数组前缀和

一维数组差分

二维数组差分

双指针

最长连续不重复子序列

数组元素的目标和

位运算

单调队列和单调栈

滑动窗口的最大值

下一个更大元素Ⅰ

并查集

模板

堆

第k个元素 + up, down模板

哈希表

DFS, BFS

层序遍历二叉树

全排列（DFS回溯）

N皇后