【Python 题解】2369. 检查数组的有效划分方法

题目概述

Leetcode 的题目 2369 要求我们检查一个整数数组nums是否可以划分为一个或多个满足特定条件的连续子数组。有效的划分条件包括：

  • 子数组由两个相等的元素组成，如 [2, 2]。
  • 子数组由三个相等的元素组成，如 [3, 3, 3]。
  • 子数组由三个连续递增的元素组成，且相邻元素之间差值为 1，如 [4, 5, 6]。

如果数组至少存在一种有效划分，则返回true；否则返回false。

示例分析

  • 示例 1：nums = [4, 4, 4, 5, 6]可以划分为 [4, 4] 和 [4, 5, 6]，因此返回true。
  • 示例 2：nums = [1, 1, 1, 2]不满足任何划分条件，因此返回false。

解题思路

采用动态规划策略，我们定义一个布尔数组dp，其中dp[i]表示数组的前i个元素是否可以有效地划分。遍历数组，对于每个位置i，尝试以下三种划分方式：

  1. 子数组由最后两个相等的元素组成。
  2. 子数组由最后三个相等的元素组成。
  3. 子数组由最后三个连续递增的元素组成。

算法流程

  1. 初始化 dp[0] 为 true，表示空数组可以有效划分。
  2. 对于每个 i（从 2 开始），检查是否可以通过上述三种方式之一将数组划分到 i。
  3. 最终，dp[n]（其中 n 是数组的长度）给出了整个数组是否可以有效划分的答案。
  4. 如果任何一种方式可行，则将dp[i]设置为true。

具体来讲
初始化：

  1. 初始化 dp[0]为 true，表示空数组是可以被有效划分的。
  2. 状态转移：对于数组中的每个元素 nums[i]（从第二个元素开始），考虑以下几种情况：
    • 如果 nums[i]与 nums[i-1]相等，检查 dp[i-2]是否为 true。如果是，表示[nums[i-1], nums[i]]可以形成有效划分，设置 dp[i]为 true。
    • 如果 nums[i]、nums[i-1]和 nums[i-2]三者相等，同样检查 dp[i-3]。如果 dp[i-3]为 true，表示[nums[i-2], nums[i-1], nums[i]]可以形成有效划分，设置 dp[i]为 true。
    • 如果 nums[i]、nums[i-1]和 nums[i-2]形成连续递增序列（即 nums[i]-1 == nums[i-1]且 nums[i-1]-1 == nums[i-2]），检查 dp[i-3]。若为 true，则设置 dp[i]为 true。
  3. 结果判断：
    • 最终，检查 dp[n]的值（其中 n 是数组 nums 的长度）。如果 dp[n]为 true，则表示整个数组可以被有效划分；否则，不可以。

动态规划实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [False] * (n + 1)
        dp[0] = True  # 空数组视为有效划分

        for i in range(2, n + 1):
            if nums[i - 1] == nums[i - 2]:
                dp[i] = dp[i] or dp[i - 2]
            if i > 2 and nums[i - 1] == nums[i - 2] == nums[i - 3]:
                dp[i] = dp[i] or dp[i - 3]
            if i > 2 and nums[i - 1] - 1 == nums[i - 2] and nums[i - 2] - 1 == nums[i - 3]:
                dp[i] = dp[i] or dp[i - 3]

        return dp[n]

算法复杂度分析

  • 时间复杂度：O(N)，其中 N 是数组nums的长度，需要遍历整个数组来填充动态规划数组。
  • 空间复杂度：O(N)，用于存储动态规划数组dp，记录每个位置的划分情况。

通过动态规划，我们提供了一种高效且直观的解决方案，确保算法的优化性能，适用于类似的数组划分问题。