Hard

题目描述

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

每一步操作中，你可以分别选择两个索引 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]。

示例 2：

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

示例 3：

输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
输出：-1
解释：无法使 arr1 严格递增。

提示：

  • 1 <= arr1.length, arr2.length <= 2000
  • 0 <= arr1[i], arr2[i] <= 10^9

解题思路

这是一道动态规划题目，核心思路是考虑每个位置保持原值或替换为某个值的最小操作次数。

思路分析：

  1. 对于 arr1 的每个位置 i，我们有两种选择：保持原值 arr1[i] 或替换为 arr2 中的某个值
  2. 为了优化查找，先对 arr2 排序并去重，这样可以使用二分查找找到合适的替换值
  3. 定义状态：dp[i][j] 表示处理到位置 i，且当前值为 sorted_arr2[j] 时的最小操作次数
  4. 状态转移：
    • 如果保持 arr1[i] 不变：需要找到所有小于 arr1[i] 的前一个状态
    • 如果替换为 arr2[k]：需要找到所有小于 arr2[k] 的前一个状态，操作次数加1
  5. 使用哈希表记录每个位置的状态，减少空间复杂度

算法步骤：

  1. 对 arr2 排序去重
  2. 初始化第一个位置的状态
  3. 逐位置进行状态转移
  4. 返回最后一个位置的最小操作次数

代码实现

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(), arr2.end());
        arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
        
        // dp[prev] = min operations to make array ending with value prev
        unordered_map<int, int> dp;
        dp[-1] = 0;  // dummy start
        
        for (int i = 0; i < arr1.size(); i++) {
            unordered_map<int, int> new_dp;
            
            for (auto [prev, cost] : dp) {
                // Keep arr1[i]
                if (arr1[i] > prev) {
                    if (!new_dp.count(arr1[i]) || new_dp[arr1[i]] > cost) {
                        new_dp[arr1[i]] = cost;
                    }
                }
                
                // Replace with arr2[j]
                auto it = upper_bound(arr2.begin(), arr2.end(), prev);
                for (auto j = it; j != arr2.end(); j++) {
                    if (!new_dp.count(*j) || new_dp[*j] > cost + 1) {
                        new_dp[*j] = cost + 1;
                    }
                }
            }
            
            dp = new_dp;
        }
        
        int result = INT_MAX;
        for (auto [val, cost] : dp) {
            result = min(result, cost);
        }
        
        return result == INT_MAX ? -1 : result;
    }
};

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2 = sorted(set(arr2))
        
        # dp[prev] = min operations to make array ending with value prev
        dp = {-1: 0}  # dummy start
        
        for num in arr1:
            new_dp = {}
            
            for prev, cost in dp.items():
                # Keep original number
                if num > prev:
                    if num not in new_dp or new_dp[num] > cost:
                        new_dp[num] = cost
                
                # Replace with arr2[j]
                idx = bisect.bisect_right(arr2, prev)
                for j in range(idx, len(arr2)):
                    val = arr2[j]
                    if val not in new_dp or new_dp[val] > cost + 1:
                        new_dp[val] = cost + 1
            
            dp = new_dp
        
        return min(dp.values()) if dp else -1

public class Solution {
    public int MakeArrayIncreasing(int[] arr1, int[] arr2) {
        Array.Sort(arr2);
        var uniqueArr2 = arr2.Distinct().ToArray();
        
        // dp[prev] = min operations to make array ending with value prev
        var dp = new Dictionary<int, int> { [-1] = 0 }; // dummy start
        
        foreach (int num in arr1) {
            var newDp = new Dictionary<int, int>();
            
            foreach (var kvp in dp) {
                int prev = kvp.Key;
                int cost = kvp.Value;
                
                // Keep original number
                if (num > prev) {
                    if (!newDp.ContainsKey(num) || newDp[num] > cost) {
                        newDp[num] = cost;
                    }
                }
                
                // Replace with arr2[j]
                int idx = Array.BinarySearch(uniqueArr2, prev);
                if (idx < 0) idx = ~idx;
                else idx++;
                
                for (int j = idx; j < uniqueArr2.Length; j++) {
                    int val = uniqueArr2[j];
                    if (!newDp.ContainsKey(val) || newDp[val] > cost + 1) {
                        newDp[val] = cost + 1;
                    }
                }
            }
            
            dp = newDp;
        }
        
        return dp.Count > 0 ? dp.Values.Min() : -1;
    }
}

var makeArrayIncreasing = function(arr1, arr2) {
    arr2.sort((a, b) => a - b);
    arr2 = [...new Set(arr2)];
    
    const n = arr1.length;
    const m = arr2.length;
    const INF = Number.MAX_SAFE_INTEGER;
    
    let dp = new Map();
    dp.set(-1, 0);
    
    for (let i = 0; i < n; i++) {
        let newDp = new Map();
        
        for (let [prev, cost] of dp) {
            if (arr1[i] > prev) {
                const key = arr1[i];
                newDp.set(key, Math.min(newDp.get(key) || INF, cost));
            }
            
            let left = 0, right = m - 1;
            let idx = -1;
            while (left <= right) {
                let mid = Math.floor((left + right) / 2);
                if (arr2[mid] > prev) {
                    idx = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            if (idx !== -1) {
                const key = arr2[idx];
                newDp.set(key, Math.min(newDp.get(key) || INF, cost + 1));
            }
        }
        
        dp = newDp;
    }
    
    let result = INF;
    for (let cost of dp.values()) {
        result = Math.min(result, cost);
    }
    
    return result === INF ? -1 : result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n₁ × n₂ × log n₂)，其中 n₁ 是 arr1 长度，n₂ 是 arr2 长度。对于每个位置，最多有 O(n₂) 个状态，每个状态需要 O(n₂) 次转移，二分查找需要 O(log n₂)
空间复杂度O(n₂)，dp 哈希表最多存储 O(n₂) 个状态

相关题目