4-20每日

1187. 使数组严格递增

给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。

每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。

如果无法让 arr1 严格递增，请返回 -1。

示例 1：

输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
输出：1
解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。

题解：动态规划

首先需要将 arr2 排序去重，并记为 list。

定义 dp[i] [j] 表示对于 arr1 的前 i 个元素，且替换了 j 个元素之后，序列的末尾数字的最小值。

将 dp 数组初始化，对于 dp[0] [0]，为了方便后面的转移，其值设为 -1。

对于 dp[i] [j]，有以下几种情况：

• 如果当前 arr1[i-1] 大于 dp[ i-1] [j]，说明不用替换，直接添加 arr1[ i-1]。
• 如果 j > 0，且 dp[ i-1] [ j-1] 不为 INF，说明可以选择替换掉前面的某个数字，使得后面更容易增加。此时找到 list 中大于 dp[ i-1] [ j-1] 的最小值进行替换。
• 如果 i == n 且 dp[i] [j] 不为 INF，说明已经处理完所有元素且序列严格递增，直接返回 j。

最终返回如果需要替换的次数，即为 dp[n] [j] 中最小不为 INF 的 j 值。

const INF = 0x3f3f3f3f;
var makeArrayIncreasing = function(arr1, arr2) {
    arr2.sort((a, b) => a - b); // 将 arr2 排序
    const list = [];
    let prev = -1;
    for (const num of arr2) { // 去重
        if (num !== prev) {
            list.push(num);
            prev = num;
        }
    }
    const n = arr1.length;
    const m = list.length;
    const dp = new Array(n + 1).fill(0).map(() => new Array(Math.min(m, n) + 1).fill(INF)); // 初始化 dp 数组
    dp[0][0] = -1; // 为了方便后面的转移，设 dp[0][0] = -1
    for (let i = 1; i <= n; i++) &#123;
        for (let j = 0; j <= Math.min(i, m); j++) &#123;
            if (arr1[i - 1] > dp[i - 1][j]) &#123; // 如果当前元素大于序列的最后一个元素
                dp[i][j] = arr1[i - 1];
            &#125;
            if (j > 0 && dp[i - 1][j - 1] !== INF) &#123; // 如果可以进行替换操作
                const idx = binarySearch(list, j - 1, dp[i - 1][j - 1]); // 查找严格大于 dp[i - 1][j - 1] 的最小元素
                if (idx !== list.length) &#123;
                    dp[i][j] = Math.min(dp[i][j], list[idx]);
                &#125;
            &#125;
            if (i === n && dp[i][j] !== INF) &#123; // 如果已经处理完所有元素且序列严格递增，直接返回替换次数
                return j;
            &#125;
        &#125;
    &#125;
    return -1; // 如果无法使 arr1 严格递增，返回 -1
&#125;

const binarySearch = (list, low, target) => &#123;
    let high = list.length;
    while (low < high) &#123; // 二分查找
        const mid = low + Math.floor((high - low) / 2);
        if (list[mid] > target) &#123;
            high = mid;
        &#125; else &#123;
            low = mid + 1;
        &#125;
    &#125;
    return low;
&#125;;