題目鏈接

Leetcode.2369 檢查數組是否存在有效劃分 rating : 1780

題目描述

給你一個下標從 $0$ 開始的整數數組 $nums$ ，你必須將數組劃分為一個或多個 連續 子數組。

如果獲得的這些子數組中每個都能滿足下述條件 之一 ，則可以稱其為數組的一種 有效 劃分：

1. 子數組 恰 由 $2$ 個相等元素組成，例如，子數組 $[2,2]$ 。
2. 子數組 恰 由 $3$ 個相等元素組成，例如，子數組 $[4,4,4]$ 。
3. 子數組 恰 由 $3$ 個連續遞增元素組成，并且相鄰元素之間的差值為 $1$ 。例如，子數組 $[3,4,5]$ ，但是子數組 $[1,3,5]$ 不符合要求。

如果數組 至少 存在一種有效劃分，返回 true ，否則，返回 false 。

示例 1：

輸入：nums = [4,4,4,5,6]
輸出：true
解釋：數組可以劃分成子數組 [4,4] 和 [4,5,6] 。
這是一種有效劃分，所以返回 true 。

示例 2：

輸入：nums = [1,1,1,2]
輸出：false
解釋：該數組不存在有效劃分。

提示：

• $2\le nums.length\le 10^5$
• $1\le nums[i]\le 10^6$

解法：dp

我們定義 $f(i)$ 考慮 $nums$ 中的前 $i$ 個數是否存在有效劃分。根據定義，$nums$ 有 $n$ 個元素，那么 $f(n)$ 就是最終要返回的答案。

我們直接考慮前 $i$ 個數：

1. 如果 $i\ge 2$ 并且 $nums[i]=nums[i?1]$，那么 $f[i]=f[i?2]$；
2. 如果 $i\ge 3$ ：

• 如果 $nums[i?2]=nums[i?1]andnums[i?1]=nums[i]$，那么 $f[i]=f[i?3]$；
• 如果 $nums[i?2]+1=nums[i?1]andnums[i?1]+1=nums[i]$，那么 $f[i]=f[i?3]$；

只要上述三種情況有一個為真，那么 $f[i]$ 就為真！

初始時，$f[0]=true$，即沒有元素也是一種有效劃分！

注意： $f[1]$ 表示第一個元素，而 $nums[0]$ 表示第一個元素。所以關于 $nums$ ，下標都要減 $1$！

最終：

1. 如果 $i\ge 2$ 并且 $nums[i?1]=nums[i?2]$，那么 $f[i]=f[i?2]$；
2. 如果 $i\ge 3$ ：

• 如果 $nums[i?3]=nums[i?2]andnums[i?2]=nums[i?1]$，那么 $f[i]=f[i?3]$；
• 如果 $nums[i?3]+1=nums[i?2]andnums[i?2]+1=nums[i?1]$，那么 $f[i]=f[i?3]$；

時間復雜度：$O(n)$

C++代碼：

class Solution {
public:bool validPartition(vector<int>& nums) {int n = nums.size();vector<int> f(n + 1);f[0] = 1;for(int i = 2;i <= n;i++){if(nums[i - 1] == nums[i - 2]) f[i] |= f[i - 2];if(i >= 3){if(nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) f[i] |= f[i - 3];if(nums[i - 3] + 1 == nums[i - 2] && nums[i - 2] + 1 == nums[i - 1]) f[i] |= f[i - 3];}}return f[n];}
};