2023-07-15：給你一個 非遞減 的正整數(shù)數(shù)組 nums 和整數(shù) K，

判斷該數(shù)組是否可以被分成一個或幾個 長度至少 為 K 的 不相交的遞增子序列。

輸入：nums = [1,2,2,3,3,4,4], K = 3。

輸出：true。

答案2023-07-15：

大體步驟如下：

1.初始化計數(shù)變量?cnt?和最大計數(shù)變量?maxCnt，初始值都為 1。

2.從索引 1 開始遍歷數(shù)組?nums：

• ??如果?nums[i-1]?不等于?nums[i]，說明遇到了一個新的遞增序列，更新?maxCnt?為之前的計數(shù)?cnt?和?maxCnt?中的較大值，并將?cnt?重置為 1。

• ??否則，遞增序列繼續(xù)，將?cnt?自增 1。

3.遍歷結束后，再次更新?maxCnt?為最后一個遞增序列的計數(shù)?cnt?和?maxCnt?中的較大值。

4.判斷長度為?len(nums)?除以?maxCnt?后是否大于等于?k，如果是，返回?true；否則，返回?false。

5.在?main?函數(shù)中，定義數(shù)組?nums?和整數(shù)?k。

6.調(diào)用函數(shù)?canDivideIntoSubsequences(nums, k)?并將結果賦給變量?result。

7.輸出結果?Result: true。

時間復雜度： 遍歷數(shù)組?nums?的時間復雜度為 O(n)，其中 n 是數(shù)組?nums?的長度。 因此，整個算法的時間復雜度為 O(n)。

空間復雜度： 算法使用了常數(shù)級別的額外空間，不隨輸入規(guī)模變化，所以空間復雜度為 O(1)。

go完整代碼如下：

package?main

import?(
????"fmt"
)

func?canDivideIntoSubsequences(nums?[]int,?k?int)?bool?{
????cnt?:=?1
????maxCnt?:=?1

????for?i?:=?1;?i?<?len(nums);?i++?{
????????if?nums[i-1]?!=?nums[i]?{
????????????maxCnt?=?max(maxCnt,?cnt)
????????????cnt?=?1
????????}?else?{
????????????cnt++
????????}
????}

????maxCnt?=?max(maxCnt,?cnt)
????return?len(nums)/maxCnt?>=?k
}

func?max(a,?b?int)?int?{
????if?a?>?b?{
????????return?a
????}
????return?b
}

func?main()?{
????nums?:=?[]int{1,?2,?2,?3,?3,?4,?4}
????k?:=?3

????result?:=?canDivideIntoSubsequences(nums,?k)
????fmt.Println("Result:",?result)
}

rust完整代碼如下：

fn?can_divide_into_subsequences(nums:?&[i32],?k:?i32)?->?bool?{
????let?mut?cnt?=?1;
????let?mut?max_cnt?=?1;

????for?i?in?1..nums.len()?{
????????if?nums[i?-?1]?!=?nums[i]?{
????????????max_cnt?=?max_cnt.max(cnt);
????????????cnt?=?1;
????????}?else?{
????????????cnt?+=?1;
????????}
????}

????max_cnt?=?max_cnt.max(cnt);
????nums.len()?as?i32?/?max_cnt?>=?k
}

fn?main()?{
????let?nums?=?vec![1,?2,?2,?3,?3,?4,?4];
????let?k?=?3;

????let?result?=?can_divide_into_subsequences(&nums,?k);
????println!("Result:?{}",?result);
}


c++完整代碼如下：

#include?<iostream>
#include?<vector>
#include?<algorithm>

using?namespace?std;

bool?canDivideIntoSubsequences(vector<int>&?nums,?int?k)?{
????int?cnt?=?1;
????int?maxCnt?=?1;

????for?(int?i?=?1;?i?<?nums.size();?i++)?{
????????if?(nums[i?-?1]?!=?nums[i])?{
????????????maxCnt?=?max(maxCnt,?cnt);
????????????cnt?=?1;
????????}
????????else?{
????????????cnt++;
????????}
????}

????maxCnt?=?max(maxCnt,?cnt);
????return?nums.size()?/?maxCnt?>=?k;
}

int?main()?{
????vector<int>?nums?=?{?1,?2,?2,?3,?3,?4,?4?};
????int?k?=?3;

????bool?result?=?canDivideIntoSubsequences(nums,?k);
????cout?<<?"Result:?"?<<?boolalpha?<<?result?<<?endl;

????return?0;
}

c完整代碼如下：

#include?<stdio.h>

int?canDivideIntoSubsequences(int?nums[],?int?length,?int?k)?{
????int?cnt?=?1;
????int?maxCnt?=?1;

????for?(int?i?=?1;?i?<?length;?i++)?{
????????if?(nums[i?-?1]?!=?nums[i])?{
????????????if?(maxCnt?<?cnt)?{
????????????????maxCnt?=?cnt;
????????????}
????????????cnt?=?1;
????????}
????????else?{
????????????cnt++;
????????}
????}

????if?(maxCnt?<?cnt)?{
????????maxCnt?=?cnt;
????}

????return?(length?/?maxCnt)?>=?k;
}

int?main()?{
????int?nums[]?=?{?1,?2,?2,?3,?3,?4,?4?};
????int?length?=?sizeof(nums)?/?sizeof(nums[0]);
????int?k?=?3;

????int?result?=?canDivideIntoSubsequences(nums,?length,?k);
????printf("Result:?%s\n",?result???"true"?:?"false");

????return?0;
}