1121. Divide Array Into Increasing Sequences
Given a non-decreasing array of positive integers nums
and an integer K
, find out if this array can be divided into one or more disjoint increasing subsequences of length at least K
.
Example 1:
Input: nums = [1,2,2,3,3,4,4], K = 3 Output: true Explanation: The array can be divided into the 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.
Note:
1 <= nums.length <= 10^5
1 <= K <= nums.length
1 <= nums[i] <= 10^5
Rust Solution
struct Solution;
impl Solution {
fn can_divide_into_subsequences(nums: Vec<i32>, k: i32) -> bool {
let n = nums.len();
let mut cur = 1;
let mut groups = 1;
for i in 1..n {
if nums[i] == nums[i - 1] {
cur += 1;
} else {
cur = 1;
}
groups = groups.max(cur);
}
n >= k as usize * groups
}
}
#[test]
fn test() {
let nums = vec![1, 2, 2, 3, 3, 4, 4];
let k = 3;
let res = true;
assert_eq!(Solution::can_divide_into_subsequences(nums, k), res);
let nums = vec![5, 6, 6, 7, 8];
let k = 3;
let res = false;
assert_eq!(Solution::can_divide_into_subsequences(nums, k), res);
}
Having problems with this solution? Click here to submit an issue on github.