这是一个非常经典的算法题，考察了对最长公共子序列 (LCS) 和 最长递增子序列 (LIS) 的转化思维。

核心思路分析

这道题的本质是：我们需要在 arr 中插入最少的元素，使得 target 成为 arr 的子序列。
换句话说，我们要找到 target 和 arr 的最长公共子序列 (LCS)。
最少操作次数 = target 的长度 - 最长公共子序列的长度。

为什么不能直接用 LCS？
通常求 LCS 使用动态规划，时间复杂度是 O(M times N)。但这道题的数据范围是 10^5，如果用 O(M times N) 会超时。

关键优化点
题目中有一个非常重要的条件：target 数组中的元素互不相同。
利用这个条件，我们可以将问题转化为 最长递增子序列 (LIS) 问题，从而将时间复杂度降低到 O(N log M)。

转化步骤：
1.  建立映射：用一个哈希表记录 target 中每个数字对应的下标（索引）。
2.  过滤与映射：遍历 arr，如果 arr 中的数字存在于 target 中，就将其替换为该数字在 target 中的下标。
3.  求解 LIS：在这个由下标组成的新数组中，寻找最长递增子序列。
    *   原理：因为 target 的下标是严格递增的（0, 1, 2...），所以 arr 中对应的下标序列如果是递增的，就说明这些元素在 target 中的相对顺序是正确的，构成了公共子序列。

Java 代码实现

import java.util.*;

class Solution {
    public int minOperations(int[] target, int[] arr) {
        // 1. 建立 target 数值到下标的映射
        // 例如 target = [5, 1, 3] -> map: {5:0, 1:1, 3:2}
        Map posMap = new HashMap();
        for (int i = 0; i  lis = new ArrayList();

        for (int num : arr) {
            // 只关注存在于 target 中的数字
            if (posMap.containsKey(num)) {
                int idx = posMap.get(num);
                
                // 在 lis 中二分查找第一个 >= idx 的位置
                int left = 0;
                int right = lis.size();
                
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (lis.get(mid) < idx) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }

                // 如果 idx 比 lis 中所有元素都大，则追加到末尾
                if (left == lis.size()) {
                    lis.add(idx);
                } else {
                    // 否则替换掉该位置的元素（贪心策略：让序列增长得更慢，潜力更大）
                    lis.set(left, idx);
                }
            }
        }

        // 3. 最少操作数 = target 总长度 - 最长公共子序列长度
        return target.length - lis.size();
    }
}

复杂度分析

*   时间复杂度: O(M + N log M)
    *   构建哈希表需要 O(M)，其中 M 是 target 的长度。
    *   遍历 arr 需要 O(N)，其中 N 是 arr 的长度。
    *   在遍历过程中，对每个有效元素进行二分查找需要 O(log K)，其中 K 是当前 LIS 的长度（最坏情况 K le M）。
    *   总体优于传统的 O(MN) 动态规划。
*   空间复杂度: O(M)
    *   哈希表存储 target 的映射关系。
    *   lis 列表存储递增序列。

举例说明

假设 target = [5, 1, 3], arr = [9, 4, 2, 3, 4]

1.  映射: {5: 0, 1: 1, 3: 2}
2.  转化 arr:
    *   9, 4, 2 不在 map 中，忽略。
    *   3 在 map 中，对应下标 2。
    *   4 不在 map 中，忽略。
    *   得到的下标序列是 [2]。
3.  求 LIS: 序列 [2] 的最长递增子序列长度为 1。
4.  结果: 3 (target长度) - 1 = 2。需要插入 5 和 1。