[LeetCode] 1187. Make Array Strictly Increasing

[grandyang]

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace `5` with `2`, then `arr1 = [1, 2, 3, 6, 7]`.

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace `5` with `3` and then replace `3` with `4`. `arr1 = [1, 3, 4, 6, 7]`.

Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make `arr1` strictly increasing.

Constraints:

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

这道题给了两个数组 arr1 和 arr2，说是可以用 arr2 中的数字来替换 arr1 中的数字，问最少需要替换多少次才能使 arr1 中的数字严格有序。所谓严格有序，就是必须是数字必须从小到大，而且不能有相等的数字出现。而且 arr2 中的每个数字只能使用一次，不过这点说不说都无所谓，因为要求严格递增，用相同的数字替换两次肯定也不符合题意。再来考虑，都是什么情况下需要替换数字呢，可以参考例子中的情况，当后面的数字小于相当的数字时，就要替换，那究竟是替换当前的数字为小一些的数字，还是替换后面的数字为大一些的数字呢？都有可能，需要考虑所有的情况，这样一来，整个问题就变的相当复杂了，基本上贪婪算法就不太可能了，这也算能对的其 Hard 的身价了。这里若是要替换后面的数字为较大的数字，那么就需要在 arr2 中找到比当前数字大的数字，为了让整个数组更容易的递增，那么这个较大数应该尽量越小越好，所以就是要找到第一个比当前数字大的数。为了更容易的在 arr2 中查找，而不是每次都遍历整个数组，需要给 arr2 排个序，然后用二分搜索来查找更高效一些，这里也可以将 arr2 放到一个 TreeSet 中，利用其自动排序的特点，之后再进行二分搜索就行了。这道题的正确解法是用动态规划 Dynamic Programming，这里的 dp 表达式比较难想，一般来说，dp 值都是定义为题目中要求的值，而这道题是个例外，这里的 dp[i][j] 表示对于数组中的前j个数字组成的子数组中，需要替换i次可以使得其变为严格递增，且第j个数字的最小值为 dp[i][j]。这里的 dp 值不是定义为替换次数，而是第j个数字的最小值（可能是替换后的值），因为要保证数组严格递增，最后一个数字的大小很重要，这是个关键信息，而这个数字的大小跟数组坐标之间没有啥必然联系，所以这个信息不太好放到 dp 数组的坐标中，而所求的替换次数跟数组长度是相关的，因为其不可能超过数组的总长度，最差的情况也就是将整个 arr1 数组都替换了（当然还需要考虑 arr2 的长度）。

接下来就来考虑状态转移方程怎么写，由于这里的j表示前j个数字，那么第j个数字实际上是 arr1[j-1]，若第j个数字大于 dp[i][j-1]，这里表示对于前 j-1 个数字，替换i次可以使得其严格递增，且第 j-1 个数字为 dp[i][j-1]，这样的话就不需要额外的替换操作，还是严格递增增的，则 dp[i][j] 可以赋值为 arr1[j-1]。若此时i大于0，说明之前已经进行过替换操作，则上一个操作状态是 dp[i-1][j-1]，当前操作是从 arr2 中选一个数字替换 arr1 的第j个数字，这里就要在 arr2 中选择第一个大于 dp[i-1][j-1] 的数字，若存在的话，就用这个数字来更新 dp[i][j] 的值。若某个时刻j等于n了，说明已经到 arr1 的末尾了，若此时 dp[i][j] 不等于 INT_MAX（初始值），说明是可以将整个 arr1 替换成严格递增的数组的，替换次数就是i，直接返回即可。最终循环退出了，返回 -1，参见代码如下：

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        if (n == 1) return 0;
        set<int> st(arr2.begin(), arr2.end());
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX));
        dp[0][0] = INT_MIN;
        for (int j = 1; j <= n; ++j) {
            for (int i = 0; i <= j; ++i) {
                if (arr1[j - 1] > dp[i][j - 1]) {
                    dp[i][j] = arr1[j - 1];
                }
                if (i > 0) {
                    auto it = st.upper_bound(dp[i - 1][j - 1]);
                    if (it != st.end()) dp[i][j] = min(dp[i][j], *it);
                }  
                if (j == n && dp[i][j] != INT_MAX) return i;
            }
        }
        return -1;
    }
};

Github 同步地址:

#1187

参考资料：

https://leetcode.com/problems/make-array-strictly-increasing/

https://leetcode.com/problems/make-array-strictly-increasing/discuss/377403/Python-DP-solution-with-explanation.

https://leetcode.com/problems/make-array-strictly-increasing/discuss/377680/Simple-Java-DP-Solution-%2B-TreeSet-with-Explanation-beats-100

LeetCode All in One 题目讲解汇总(持续更新中...)