Question

1121. 将数组分成几个递增序列

English Version

题目描述

给你一个 非递减 的正整数数组 nums 和整数 K，判断该数组是否可以被分成一个或几个 长度至少 为 K 的 不相交的递增子序列。

 

示例 1：

输入：nums = [1,2,2,3,3,4,4], K = 3
输出：true
解释：
该数组可以分成两个子序列 [1,2,3,4] 和 [2,3,4]，每个子序列的长度都至少是 3。

示例 2：

输入：nums = [5,6,6,7,8], K = 3
输出：false
解释：
没有办法根据条件来划分数组。

 

提示：

1. 1 <= nums.length <= 10^5
2. 1 <= K <= nums.length
3. 1 <= nums[i] <= 10^5

解法

方法一：脑筋急转弯

我们假设可以将数组分成 $m$ 个长度至少为 $k$ 的严格递增子序列，如果数组中出现次数最多的数字的个数为 $cnt$，那么这 $cnt$ 个数字必须在不同的子序列中，所以 $m \geq cnt$，又因为 $m$ 个子序列的长度至少为 $k$，因此，子序列的个数越少越好，所以 $m = cnt$。那么 $cnt \times k \leq n$，才能满足题意。因此，我们只需要统计数组中出现次数最多的数字的个数 $cnt$，然后判断 $cnt \times k \leq n$ 即可。如果是，返回 true，否则返回 false。

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

class Solution:
  def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:
    mx = max(len(list(x)) for _, x in groupby(nums))
    return mx * k <= len(nums)

class Solution {
  public boolean canDivideIntoSubsequences(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    int mx = 0;
    for (int x : nums) {
      mx = Math.max(mx, cnt.merge(x, 1, Integer::sum));
    }
    return mx * k <= nums.length;
  }
}

class Solution {
public:
  bool canDivideIntoSubsequences(vector<int>& nums, int k) {
    int cnt = 0;
    int a = 0;
    for (int& b : nums) {
      cnt = a == b ? cnt + 1 : 1;
      if (cnt * k > nums.size()) {
        return false;
      }
      a = b;
    }
    return true;
  }
};

func canDivideIntoSubsequences(nums []int, k int) bool {
  cnt, a := 0, 0
  for _, b := range nums {
    cnt++
    if a != b {
      cnt = 1
    }
    if cnt*k > len(nums) {
      return false
    }
    a = b
  }
  return true
}

方法二

class Solution {
  public boolean canDivideIntoSubsequences(int[] nums, int k) {
    int cnt = 0;
    int a = 0;
    for (int b : nums) {
      cnt = a == b ? cnt + 1 : 1;
      if (cnt * k > nums.length) {
        return false;
      }
      a = b;
    }
    return true;
  }
}