2771-构造最长非递减子数组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度均为 n 。

让我们定义另一个下标从 0 开始、长度为 n 的整数数组，nums3 。对于范围 [0, n - 1] 的每个下标 i ，你可以将
nums1[i] 或 nums2[i] 的值赋给 nums3[i] 。

你的任务是使用最优策略为 nums3 赋值，以最大化 nums3 中 最长非递减子数组 的长度。

以整数形式表示并返回 nums3 中 最长非递减 子数组的长度。

注意：子数组 是数组中的一个连续非空元素序列。

示例 1：

**输入：** nums1 = [2,3,1], nums2 = [1,2,1]
**输出：** 2
**解释：** 构造 nums3 的方法之一是： 
nums3 = [nums1[0], nums2[1], nums2[2]] => [2,2,1]
从下标 0 开始到下标 1 结束，形成了一个长度为 2 的非递减子数组 [2,2] 。 
可以证明 2 是可达到的最大长度。

示例 2：

**输入：** nums1 = [1,3,2,1], nums2 = [2,2,3,4]
**输出：** 4
**解释：** 构造 nums3 的方法之一是： 
nums3 = [nums1[0], nums2[1], nums2[2], nums2[3]] => [1,2,3,4]
整个数组形成了一个长度为 4 的非递减子数组，并且是可达到的最大长度。

示例 3：

**输入：** nums1 = [1,1], nums2 = [2,2]
**输出：** 2
**解释：** 构造 nums3 的方法之一是： 
nums3 = [nums1[0], nums1[1]] => [1,1] 
整个数组形成了一个长度为 2 的非递减子数组，并且是可达到的最大长度。

提示：

  • 1 <= nums1.length == nums2.length == n <= 105
  • 1 <= nums1[i], nums2[i] <= 109

下午两点【b站@灵茶山艾府】 直播讲题，欢迎关注！

前置知识：动态规划入门

详见 动态规划入门：从记忆化搜索到递推【基础算法精讲 17】

思路

为方便后面翻译成递推，这里从右往左递归。

定义 dfs}(i,j) 表示以 nums}_j[i] 结尾的最长非递减子数组的长度。

用「枚举选哪个」来思考：

  • 如果 nums}_1[i-1]\le \textit{nums}_j[i]，那么下一步选 nums}_1[i-1]，有 dfs}(i,j) = \textit{dfs}(i-1,0)+1。
  • 如果 nums}_2[i-1]\le \textit{nums}_j[i]，那么下一步选 nums}_2[i-1]，有 dfs}(i,j) = \textit{dfs}(i-1,1)+1。
  • 如果都不成立，那么 dfs}(i,j)=1。

这几种情况取最大值，即为 dfs}(i,j)。

递归边界：dfs}(0)=1。

递归入口：dfs}(i,j)。遍历所有 i,j 取 dfs}(i,j) 的最大值，即为答案。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        nums = (nums1, nums2)
        @cache
        def dfs(i: int, j: int) -> int:
            if i == 0: return 1
            res = 1
            if nums1[i - 1] <= nums[j][i]:
                res = dfs(i - 1, 0) + 1
            if nums2[i - 1] <= nums[j][i]:
                res = max(res, dfs(i - 1, 1) + 1)
            return res
        return max(dfs(i, j) for j in range(2) for i in range(len(nums1)))
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func maxNonDecreasingLength(nums1, nums2 []int) (ans int) {
	n := len(nums1)
	nums := [2][]int{nums1, nums2}
	memo := make([][2]int, n)
	for i := range memo {
		memo[i] = [2]int{-1, -1} // -1 表示没有计算过
	}
	var dfs func(int, int) int
	dfs = func(i, j int) int {
		if i == 0 {
			return 1
		}
		p := &memo[i][j]
		if *p != -1 { // 之前计算过
			return *p
		}
		res := 1
		if nums1[i-1] <= nums[j][i] {
			res = dfs(i-1, 0) + 1
		}
		if nums2[i-1] <= nums[j][i] {
			res = max(res, dfs(i-1, 1)+1)
		}
		*p = res // 记忆化
		return res
	}
	for j := 0; j < 2; j++ {
		for i := 0; i < n; i++ {
			ans = max(ans, dfs(i, j))
		}
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }

然后按照 视频 中讲的，1:1 翻译成递推。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        nums = (nums1, nums2)
        f = [[1, 1] for _ in range(n)]
        for i in range(1, n):
            for j in range(2):
                if nums1[i - 1] <= nums[j][i]:
                    f[i][j] = f[i - 1][0] + 1
                if nums2[i - 1] <= nums[j][i]:
                    f[i][j] = max(f[i][j], f[i - 1][1] + 1)
        return max(map(max, f))
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxNonDecreasingLength(nums1, nums2 []int) int {
	ans, n := 1, len(nums1)
	nums := [2][]int{nums1, nums2}
	f := make([][2]int, n)
	f[0] = [2]int{1, 1}
	for i := 1; i < n; i++ {
		f[i] = [2]int{1, 1}
		for j := 0; j < 2; j++ {
			if nums1[i-1] <= nums[j][i] {
				f[i][j] = f[i-1][0] + 1
			}
			if nums2[i-1] <= nums[j][i] {
				f[i][j] = max(f[i][j], f[i-1][1]+1)
			}
		}
		ans = max(ans, max(f[i][0], f[i][1]))
	}
	return ans
}

func max(a, b int) int { if b > a { return b }; return a }

由于 f[i] 只用到 f[i-1]，所以可以去掉第一个维度。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        ans = f0 = f1 = 1
        for (x0, y0), (x1, y1) in pairwise(zip(nums1, nums2)):
            f = g = 1
            if x0 <= x1: f = f0 + 1
            if y0 <= x1: f = max(f, f1 + 1)
            if x0 <= y1: g = f0 + 1
            if y0 <= y1: g = max(g, f1 + 1)
            f0, f1 = f, g
            ans = max(ans, f0, f1)
        return ans
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func maxNonDecreasingLength(nums1, nums2 []int) int {
	ans, n := 1, len(nums1)
	f0, f1 := 1, 1
	for i := 1; i < n; i++ {
		f, g := 1, 1
		if nums1[i-1] <= nums1[i] {
			f = f0 + 1
		}
		if nums2[i-1] <= nums1[i] {
			f = max(f, f1+1)
		}
		if nums1[i-1] <= nums2[i] {
			g = f0 + 1
		}
		if nums2[i-1] <= nums2[i] {
			g = max(g, f1+1)
		}
		f0, f1 = f, g
		ans = max(ans, max(f0, f1))
	}
	return ans
}

func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(n)，其中 n 为 nums}_1 的长度。动态规划的时间复杂度 = 状态个数 \times 单个状态的计算时间。本题中状态个数等于 \mathcal{O}(n)，单个状态的计算时间为 \mathcal{O}(1)，所以动态规划的时间复杂度为 \mathcal{O}(n)。
  • 空间复杂度：\mathcal{O}(1)。仅用到若干额外变量。

思考题

如果把「子数组」改成「子序列」呢？

 Comments
On this page
2771-构造最长非递减子数组
  1. 前置知识：动态规划入门
  2. 思路
  3. 思考题