Leetcode 3269. 构建两个递增数组

1.题目基本信息

1.1.题目描述

给定两个只包含 0 和 1 的整数数组 nums1 和 nums2，你的任务是执行下面操作后使数组 nums1 和 nums2 中 最大 可达数字 尽可能小。

将每个 0 替换为正偶数，将每个 1 替换为正奇数。在替换后，两个数组都应该 递增 并且每个整数 至多 被使用一次。

返回执行操作后最小的最大可达数字。

1.2.题目地址

https://leetcode.cn/problems/constructing-two-increasing-arrays/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

第一步，预处理。构建nextValue函数，计算在当前最大值为val，nums数组中的值为num时，求下一个合法的最小值

第二步，状态定义。dp[i][j][0]表示在nums1[:i]和nums2[:j]的子问题中，最后填入nums1的最小最大值，dp[i][j][1]表示最后填入nums2的最小最大值。

第三步，状态初始化。默认为inf，dp[0][0]=[0,0]，dp[0][j][1]=NEXT(nums2[:j])，dp[i][0][0]=NEXT(nums1[:i])（其中NEXT函数功能为求单数组合法填写到最后的最小最大值）

第四步，状态转移。dp[i][j][0]=NEXT_VALUE(min(dp[i-1][j]),nums1[i-1])，dp[i][j]=NEXT_VALUE(min(dp[i][j-1]),nums2[j-1])（其中NEXT_VALUE在已知前一个最大值和当前num的情况下，获取下一个需要填的最小值）

第五步，最终的min(dp[-1][-1])即为题解

3.解题代码

Python代码

class Solution:def minLargest(self, nums1: List[int], nums2: List[int]) -> int:# 思路：动态规划m, n = len(nums1), len(nums2)# 第一步，预处理。构建nextValue函数，计算在当前最大值为val，nums数组中的值为num时，求下一个合法的最小值def nextValue(val:int, num:int) -> int:if val % 2 == 0:if num == 0:return val + 2else:return val + 1else:if num == 0:return val + 1else:return val + 2# 第二步，状态定义。dp[i][j][0]表示在nums1[:i]和nums2[:j]的子问题中，最后填入nums1的最小最大值，dp[i][j][1]表示最后填入nums2的最小最大值。dp = [[[inf, inf] for _ in range(n + 1)] for _ in range(m + 1)]# 第三步，状态初始化。默认为inf，dp[0][0]=[0,0]，dp[0][j][1]=NEXT(nums2[:j])，dp[i][0][0]=NEXT(nums1[:i])（其中NEXT函数功能为求单数组合法填写到最后的最小最大值）dp[0][0] = [0, 0]for j in range(1, n + 1):dp[0][j][1] = nextValue(min(dp[0][j - 1]), nums2[j - 1])for i in range(1, m + 1):dp[i][0][0] = nextValue(min(dp[i - 1][0]), nums1[i - 1])# print(dp)# 第四步，状态转移。dp[i][j][0]=NEXT_VALUE(min(dp[i-1][j]),nums1[i-1])，dp[i][j]=NEXT_VALUE(min(dp[i][j-1]),nums2[j-1])（其中NEXT_VALUE在已知前一个最大值和当前num的情况下，获取下一个需要填的最小值）for i in range(1, m + 1):for j in range(1, n + 1):dp[i][j][0] = nextValue(min(dp[i - 1][j]), nums1[i - 1])dp[i][j][1] = nextValue(min(dp[i][j - 1]), nums2[j - 1])# 第五步，最终的min(dp[-1][-1])即为题解return min(dp[m][n])

4.执行结果