Medium

题目描述

给你一个按非递减顺序排列的整数数组 nums。

请你判断是否能够将 nums 分割成一个或多个子序列，且同时满足下述 两个 条件：

  • 每个子序列都是一个连续递增序列（即，每个整数 恰好 比前一个整数大 1）。
  • 所有子序列的长度至少为 3。

如果可以分割 nums 并满足上述条件，则返回 true；否则，返回 false。

数组的子序列是由原数组删除一些元素（也可以不删除）得到的一个新数组，且不改变其余元素的相对顺序。（例如，[1,3,5] 是 [1,2,3,4,5] 的一个子序列，而 [1,3,2] 不是）。

示例 1：

输入：nums = [1,2,3,3,4,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,5] --> 1, 2, 3
[1,2,3,3,4,5] --> 3, 4, 5

示例 2：

输入：nums = [1,2,3,3,4,4,5,5]
输出：true
解释：nums 可以分割成以下子序列：
[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5
[1,2,3,3,4,4,5,5] --> 3, 4, 5

示例 3：

输入：nums = [1,2,3,4,4,5]
输出：false
解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。

提示：

  • 1 <= nums.length <= 10^4
  • -1000 <= nums[i] <= 1000
  • nums 按非递减顺序排列

解题思路

这道题需要判断数组能否分割成多个长度至少为3的连续递增子序列。

贪心策略分析：

核心思想是贪心地构造子序列。对于当前数字，我们有两种选择：

  1. 将其接在已有的子序列末尾
  2. 开始一个新的子序列

贪心策略：优先选择第一种方案，因为这样能充分利用已有的子序列，避免产生过短的子序列。

算法步骤：

  1. 使用两个哈希表：

    • count：记录每个数字的剩余个数
    • tail：记录以每个数字结尾的子序列个数

  2. 遍历数组中的每个数字：

    • 如果该数字已用完，跳过
    • 如果存在以num-1结尾的子序列，将当前数字接上去（贪心选择）
    • 否则，尝试开始新子序列[num, num+1, num+2]
    • 如果无法形成新子序列，返回false

  3. 这种贪心策略保证了每次都做出局部最优选择，最终得到全局最优解。

时间复杂度O(n)，空间复杂度O(n)，其中n为数组长度。

代码实现

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> count, tail;
        
        // 统计每个数字的个数
        for (int num : nums) {
            count[num]++;
        }
        
        for (int num : nums) {
            if (count[num] == 0) continue;
            
            // 优先接在已有子序列后面
            if (tail[num - 1] > 0) {
                tail[num - 1]--;
                tail[num]++;
                count[num]--;
            }
            // 尝试开始新的子序列
            else if (count[num + 1] > 0 && count[num + 2] > 0) {
                count[num]--;
                count[num + 1]--;
                count[num + 2]--;
                tail[num + 2]++;
            }
            // 无法形成有效子序列
            else {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        from collections import defaultdict
        
        count = defaultdict(int)
        tail = defaultdict(int)
        
        # 统计每个数字的个数
        for num in nums:
            count[num] += 1
        
        for num in nums:
            if count[num] == 0:
                continue
            
            # 优先接在已有子序列后面
            if tail[num - 1] > 0:
                tail[num - 1] -= 1
                tail[num] += 1
                count[num] -= 1
            # 尝试开始新的子序列
            elif count[num + 1] > 0 and count[num + 2] > 0:
                count[num] -= 1
                count[num + 1] -= 1
                count[num + 2] -= 1
                tail[num + 2] += 1
            # 无法形成有效子序列
            else:
                return False
        
        return True

public class Solution {
    public bool IsPossible(int[] nums) {
        var count = new Dictionary<int, int>();
        var tail = new Dictionary<int, int>();
        
        // 统计每个数字的个数
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }
        
        foreach (int num in nums) {
            if (count.GetValueOrDefault(num, 0) == 0) continue;
            
            // 优先接在已有子序列后面
            if (tail.GetValueOrDefault(num - 1, 0) > 0) {
                tail[num - 1]--;
                tail[num] = tail.GetValueOrDefault(num, 0) + 1;
                count[num]--;
            }
            // 尝试开始新的子序列
            else if (count.GetValueOrDefault(num + 1, 0) > 0 && 
                     count.GetValueOrDefault(num + 2, 0) > 0) {
                count[num]--;
                count[num + 1]--;
                count[num + 2]--;
                tail[num + 2] = tail.GetValueOrDefault(num + 2, 0) + 1;
            }
            // 无法形成有效子序列
            else {
                return false;
            }
        }
        
        return true;
    }
}

var isPossible = function(nums) {
    const count = new Map();
    const need = new Map();
    
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    for (const num of nums) {
        if (count.get(num) === 0) continue;
        
        if (need.get(num) > 0) {
            need.set(num, need.get(num) - 1);
            need.set(num + 1, (need.get(num + 1) || 0) + 1);
        } else if (count.get(num + 1) > 0 && count.get(num + 2) > 0) {
            count.set(num + 1, count.get(num + 1) - 1);
            count.set(num + 2, count.get(num + 2) - 1);
            need.set(num + 3, (need.get(num + 3) || 0) + 1);
        } else {
            return false;
        }
        
        count.set(num, count.get(num) - 1);
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次，每次操作为常数时间
空间复杂度O(n)需要两个哈希表存储数字的计数和尾部信息

相关题目