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$.
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
Solution 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|