Skip to content

Latest commit

 

History

History
242 lines (197 loc) · 7.19 KB

File metadata and controls

242 lines (197 loc) · 7.19 KB
comments difficulty edit_url rating source tags
true
中等
1791
第 353 场周赛 Q3
数组
动态规划

English Version

题目描述

给你两个下标从 0 开始的整数数组 nums1nums2 ,长度均为 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

解法

方法一:动态规划

我们定义两个变量 $f$$g$,分别表示当前位置的最长非递减子数组长度,其中 $f$ 表示以 $nums1$ 元素为结尾的最长非递减子数组长度,而 $g$ 表示以 $nums2$ 元素为结尾的最长非递减子数组长度。初始时 $f = g = 1$,初始答案 $ans = 1$

接下来,我们在 $i \in [1, n)$ 的范围内遍历数组元素,对于每个 $i$,我们定义两个变量 $ff$$gg$,分别表示以 $nums1[i]$$nums2[i]$ 元素为结尾的最长非递减子数组长度,初始化时 $ff = gg = 1$

我们可以通过 $f$$g$ 的值来计算出 $ff$$gg$ 的值:

  • 如果 $nums1[i] \ge nums1[i - 1]$,那么 $ff = \max(ff, f + 1)$
  • 如果 $nums1[i] \ge nums2[i - 1]$,那么 $ff = \max(ff, g + 1)$
  • 如果 $nums2[i] \ge nums1[i - 1]$,那么 $gg = \max(gg, f + 1)$
  • 如果 $nums2[i] \ge nums2[i - 1]$,那么 $gg = \max(gg, g + 1)$

然后,我们更新 $f = ff$$g = gg$,并将 $ans$ 更新为 $\max(ans, f, g)$

遍历结束后,我们返回 $ans$ 即可。

时间复杂度 $O(n)$,其中 $n$ 是数组的长度。空间复杂度 $O(1)$

Python3

class Solution:
    def maxNonDecreasingLength(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        f = g = 1
        ans = 1
        for i in range(1, n):
            ff = gg = 1
            if nums1[i] >= nums1[i - 1]:
                ff = max(ff, f + 1)
            if nums1[i] >= nums2[i - 1]:
                ff = max(ff, g + 1)
            if nums2[i] >= nums1[i - 1]:
                gg = max(gg, f + 1)
            if nums2[i] >= nums2[i - 1]:
                gg = max(gg, g + 1)
            f, g = ff, gg
            ans = max(ans, f, g)
        return ans

Java

class Solution {
    public int maxNonDecreasingLength(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int f = 1, g = 1;
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            int ff = 1, gg = 1;
            if (nums1[i] >= nums1[i - 1]) {
                ff = Math.max(ff, f + 1);
            }
            if (nums1[i] >= nums2[i - 1]) {
                ff = Math.max(ff, g + 1);
            }
            if (nums2[i] >= nums1[i - 1]) {
                gg = Math.max(gg, f + 1);
            }
            if (nums2[i] >= nums2[i - 1]) {
                gg = Math.max(gg, g + 1);
            }
            f = ff;
            g = gg;
            ans = Math.max(ans, Math.max(f, g));
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maxNonDecreasingLength(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int f = 1, g = 1;
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            int ff = 1, gg = 1;
            if (nums1[i] >= nums1[i - 1]) {
                ff = max(ff, f + 1);
            }
            if (nums1[i] >= nums2[i - 1]) {
                ff = max(ff, g + 1);
            }
            if (nums2[i] >= nums1[i - 1]) {
                gg = max(gg, f + 1);
            }
            if (nums2[i] >= nums2[i - 1]) {
                gg = max(gg, g + 1);
            }
            f = ff;
            g = gg;
            ans = max(ans, max(f, g));
        }
        return ans;
    }
};

Go

func maxNonDecreasingLength(nums1 []int, nums2 []int) int {
	n := len(nums1)
	f, g, ans := 1, 1, 1
	for i := 1; i < n; i++ {
		ff, gg := 1, 1
		if nums1[i] >= nums1[i-1] {
			ff = max(ff, f+1)
		}
		if nums1[i] >= nums2[i-1] {
			ff = max(ff, g+1)
		}
		if nums2[i] >= nums1[i-1] {
			gg = max(gg, f+1)
		}
		if nums2[i] >= nums2[i-1] {
			gg = max(gg, g+1)
		}
		f, g = ff, gg
		ans = max(ans, max(f, g))
	}
	return ans
}

TypeScript

function maxNonDecreasingLength(nums1: number[], nums2: number[]): number {
    const n = nums1.length;
    let [f, g, ans] = [1, 1, 1];
    for (let i = 1; i < n; ++i) {
        let [ff, gg] = [1, 1];
        if (nums1[i] >= nums1[i - 1]) {
            ff = Math.max(ff, f + 1);
        }
        if (nums1[i] >= nums2[i - 1]) {
            ff = Math.max(ff, g + 1);
        }
        if (nums2[i] >= nums1[i - 1]) {
            gg = Math.max(gg, f + 1);
        }
        if (nums2[i] >= nums2[i - 1]) {
            gg = Math.max(gg, g + 1);
        }
        f = ff;
        g = gg;
        ans = Math.max(ans, f, g);
    }
    return ans;
}