Question

1121. Divide Array Into Increasing Sequences

中文文档

Description

Given an integer array nums sorted in non-decreasing order and an integer k, return true_ if this array can be divided into one or more disjoint increasing subsequences of length at least _k_, or _false_ otherwise_.

 

Example 1:

Input: nums = [1,2,2,3,3,4,4], k = 3
Output: true
Explanation: The array can be divided into two subsequences [1,2,3,4] and [2,3,4] with lengths at least 3 each.

Example 2:

Input: nums = [5,6,6,7,8], k = 3
Output: false
Explanation: There is no way to divide the array using the conditions required.

 

Constraints:

• 1 <= k <= nums.length <= 105
• 1 <= nums[i] <= 105
• nums is sorted in non-decreasing order.

Solutions

Solution 1: Quick Thinking

We assume that the array can be divided into $m$ strictly increasing subsequences of length at least $k$. If the number of the most frequent number in the array is $cnt$, then these $cnt$ numbers must be in different subsequences, so $m \geq cnt$. Also, since the length of $m$ subsequences is at least $k$, the fewer the number of subsequences, the better, so $m = cnt$. Therefore, $cnt \times k \leq n$ must be satisfied. Hence, we only need to count the number of the most frequent number $cnt$ in the array, and then judge whether $cnt \times k \leq n$. If it is, return true, otherwise return false.

The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $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
}

Solution 2

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;
  }
}