600数组递增操作问题

问题描述

在一个神秘的森林里，两个探险家，小智和小璇，面临着一项艰巨的任务。他们拥有两个魔法宝箱，分别装有整数列表 list1 和 list2。他们的目标是通过某种方式将 list1 转变为一个严格递增的序列。

他们可以执行的操作是：在任意时刻，选择 list1 中的一个元素和 list2 中的一个元素进行替换。具体来说，他们可以选择 list1 的某个位置 i 和 list2 的某个位置 j，并将 list1[i] 设置为 list2[j]。

现在，小智和小璇需要你帮助他们计算出，通过最少的操作次数，是否可以将 list1 变为严格递增的序列。如果可以做到，请返回所需的最少操作次数；如果不可能，请返回 -1。

测试样例

样例 1：

输入：list1 = [3, 8, 4, 10, 11], list2 = [2, 7, 5, 9]
输出：1

样例 2：

输入：list1 = [5, 9, 7, 11], list2 = [1, 6, 8, 12]
输出：1

样例 3：

输入：list1 = [1, 3, 4, 6], list2 = [2, 5]
输出：0

题解

这道题目要求通过最小的操作次数，将 list1 转变为一个严格递增的序列。可以选择将 list1 中的任意元素替换为 list2 中的任意元素。

解题思路

使用动态规划来解决这个问题。维护一个字典 pre，其中键表示当前序列的最后一个元素，值表示达到该值并且序列是严格递增的所需的最小操作次数。

1. 初始化：将 pre 初始化为 { -inf: 0 }，表示在序列开始前，最后一个元素为负无穷，操作次数为 0。
2. 遍历 list1：对于 list1 中的每一个元素 x，
   • 创建一个新的字典 cur 来记录当前状态。
   • 对于 pre 中的每一个状态 k，
     • 如果 x > k，则可以不替换，直接更新 cur[x]。
     • 使用二分查找找到 list2 中第一个大于 k 的元素 a[j]，将 cur[a[j]] 更新为 v + 1。
3. 更新状态：将 pre 更新为 cur 的副本。
4. 结果：遍历完成后，如果 cur 不为空，返回最小的操作次数，否则返回 -1。

代码实现

from typing import List
from collections import defaultdict
from bisect import bisect_right

inf = float("inf")

def solution(list1: List[int], list2: List[int]) -> int:
    a = sorted(set(list2))
    pre = defaultdict(lambda: inf)
    pre[-inf] = 0
    for i, x in enumerate(list1):
        cur = defaultdict(lambda: inf)
        for k, v in pre.items():
            if x > k:
                cur[x] = min(cur[x], v)
            j = bisect_right(a, k)
            if j < len(a):
                cur[a[j]] = min(cur[a[j]], v + 1)
        pre = cur.copy()
        if not cur:
            return -1
    return min(cur.values())

if __name__ == '__main__':
    print(solution(list1=[3, 8, 4, 10, 11], list2=[2, 7, 5, 9]) == 1)
    print(solution(list1=[5, 9, 7, 11], list2=[1, 6, 8, 12]) == 1)
    print(solution(list1=[1, 3, 4, 6], list2=[2, 5]) == 0)

复杂度分析

• 时间复杂度：$O(n ^ 2 log m)$，其中 n 是 list1 的长度，m 是 list2 的长度。主要由排序和二分查找操作决定。
• 空间复杂度：$O(m)$，用于存储动态规划的状态。