1187.使数组严格递增

链接：1187.使数组严格递增
难度：Hard
标签：数组、二分查找、动态规划、排序
简介：给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。如果无法让 arr1 严格递增，请返回 -1。

题解 1 - cpp

• 编辑时间：2023-04-20
• 执行用时：604ms
• 内存消耗：71.1MB
• 编程语言：cpp
• 解法介绍：dfs，每次记录当前下标和上一个值，如果当前值替换，应该换成最大可换的值。

class Solution {
    public:
        int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
            set<int> s;
            for (auto &num : arr2) s.insert(num);
            unordered_map<int, unordered_map<int, int>> m;
            function<int(int, int)> dfs = [&](int idx, int pre) -> int {
                if (m[idx].count(pre)) return m[idx][pre];
                if (idx == - 1) return m[idx][pre] = 0;
                int res = INT_MAX;
                if (arr1[idx] < pre) res = dfs(idx - 1, arr1[idx]);
                auto find = s.lower_bound(pre);
                if (find != s.begin()) {
                    int next = dfs(idx - 1, *(--find));
                    if (next != INT_MAX)
                    res = min(res, 1 + next);
                }
                return m[idx][pre] = res;
            };
            int res = dfs(arr1.size() - 1, INT_MAX);
            return res == INT_MAX ? -1 : res;
        }
    };

题解 2 - python

• 编辑时间：2023-04-20
• 执行用时：724ms
• 内存消耗：131.3MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2.sort()
        @cache
        def dfs(idx: int, pre: int) -> int:
            if idx == -1:
                return 0
            res = inf
            if arr1[idx] < pre:
                res = dfs(idx-1, arr1[idx])
            find = bisect_left(arr2, pre)
            if find > 0:
                res = min(res, dfs(idx-1, arr2[find - 1]) + 1)
            return res
        res = dfs(len(arr1) - 1, inf)
        return res if res != inf else -1