最长上升子序列（LIS）

题目	难度
300. 最长递增子序列	中等
354. 俄罗斯套娃信封问题	困难
1713. 得到子序列的最少操作次数	困难
2111. 使数组 K 递增的最少操作次数	困难
2407. 最长递增子序列 II	困难

题目	难度
435. 无重叠区间	中等
646. 最长数对链	中等
452. 用最少数量的箭引爆气球	中等
1691. 堆叠长方体的最大高度	困难	三维 俄罗斯套娃信封问题 但是 O(n^2)
面试题 08.13. 堆箱子	困难	类似 1691
960. 删列造序 III	困难

模板（严格递增）

func lengthOfLIS(nums []int) int {
    g := []int{}
    for _, x := range nums {
        j := sort.SearchInts(g, x)
        if j == len(g) { // >=x 的 g[j] 不存在
            g = append(g, x)
        } else {
            g[j] = x
        }
    }
    return len(g)
}

300. 最长递增子序列

import java.util.ArrayList;
import java.util.List;

public class Solution300 {
    // 动态规划
    // 时间复杂度 O(n^2)
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // 定义 dp[i] 为包含第 i 个元素的最长上升子序列长度
        int[] dp = new int[n];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                // 严格递增
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    // 贪心 + 二分查找
    // 时间复杂度 O(nlogn)
    public int lengthOfLIS2(int[] nums) {
        List<Integer> a = new ArrayList<>();
        for (int x : nums) {
            int j = searchInts(a, x);
            if (j == a.size()) a.add(x);
            else a.set(j, x);
        }
        return a.size();
    }

    private int searchInts(List<Integer> a, int key) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a.get(m) >= key) r = m;
            else l = m + 1;
        }
        return l;
    }
}

354. 俄罗斯套娃信封问题

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution354 {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return Integer.compare(o2[1], o1[1]);
            }
            return Integer.compare(o1[0], o2[0]);
        });

        // LIS
        List<Integer> a = new ArrayList<>();
        for (int[] e : envelopes) {
            int x = e[1];
            int j = searchInts(a, x);
            if (j == a.size()) a.add(x);
            else a.set(j, x);
        }
        return a.size();
    }

    private int searchInts(List<Integer> a, int key) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a.get(m) >= key) r = m;
            else l = m + 1;
        }
        return l;
    }
}

1713. 得到子序列的最少操作次数

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1713 {
    public int minOperations(int[] target, int[] arr) {
        int n = target.length;
        // 预处理下标
        Map<Integer, Integer> posMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            posMap.put(target[i], i);
        }

        List<Integer> a = new ArrayList<>();
        for (int ai : arr) {
            if (posMap.containsKey(ai)) {
                Integer x = posMap.get(ai);
                int j = searchInts(a, x);
                if (j == a.size()) a.add(x);
                else a.set(j, x);
            }
        }
        return n - a.size();
    }

    private int searchInts(List<Integer> a, int key) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a.get(m) >= key) r = m;
            else l = m + 1;
        }
        return l;
    }
}

2111. 使数组 K 递增的最少操作次数

非递减，不要求严格递增。

import java.util.ArrayList;
import java.util.List;

public class Solution2111 {
    public int kIncreasing(int[] arr, int k) {
        int len = arr.length;
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = i; j < len; j += k) {
                list.add(arr[j]);
            }
            cnt += lengthOfLIS(list);
        }
        return len - cnt;
    }

    public int lengthOfLIS(List<Integer> nums) {
        List<Integer> a = new ArrayList<>();
        for (int x : nums) {
            int j = searchInts(a, x);
            if (j == a.size()) a.add(x);
            else a.set(j, x);
        }
        return a.size();
    }

    private int searchInts(List<Integer> a, int key) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a.get(m) > key) r = m;
            else l = m + 1;
        }
        return l;
    }
}

（全文完）