难度: Hard
Submission
运行时间: 48 ms
内存: 28.0 MB
class Solution:
def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:
n = len(nums)
pre = nums[0]
cnt = 1
for num in nums[1:]:
if pre == num:
cnt += 1
else:
if cnt * k > n:
return False
cnt = 1
pre = num
return cnt * k <= n
Explain
题解通过遍历数组并统计连续相同元素的数量来判断是否能将数组分成每个序列长度至少为k的若干递增序列。核心逻辑是对每一段连续的相同元素进行计数，然后检查这个数量乘以k是否超过数组总长度，如果超过则返回False。如果没有超过，则更新计数器和前一个元素的值，继续遍历。最后一次检查是对最后一段连续相同元素的处理，确保它们的数量乘以k不超过数组长度。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def canDivideIntoSubsequences(self, nums: List[int], k: int) -> bool:
n = len(nums) # 数组总长度
pre = nums[0] # 前一个元素的值初始化为数组的第一个元素
cnt = 1 # 计数器初始化为1，表示至少有一个nums[0]
for num in nums[1:]: # 从第二个元素开始遍历数组
if pre == num: # 如果当前元素与前一个元素相同
cnt += 1 # 增加计数器
else: # 如果当前元素与前一个元素不同
if cnt * k > n: # 检查目前为止统计的数量乘以k是否大于数组长度
return False # 如果大于，则无法满足条件，直接返回False
cnt = 1 # 重置计数器为1
pre = num # 更新前一个元素的值
return cnt * k <= n # 最后检查最后一段元素是否满足条件
Explore
这种方法是基于将数组分割成若干个长度至少为k的递增序列的要求。如果某个元素出现的次数过多，即使是最小的情况下，也需要该元素重复k次来形成一个有效的子序列，这就要求整个数组提供足够的长度来容纳这些重复的子序列。如果任何一个元素的出现次数乘以k超过了数组长度，那么就不可能在不违反每个子序列至少长度为k的规则的前提下进行分割。这样的检查确保了在每个元素的频率和子序列的最小长度之间有一种平衡，是算法效率和实现的简洁性之间的折中。
如果数组中所有元素都相同，那么计数器`cnt`将会记录数组总长度，因为所有元素都是连续相同的。此时，算法会检查`cnt * k`是否小于等于数组长度`n`。如果`cnt * k`大于`n`，则算法返回`False`，表示无法将数组分割成每个序列长度至少为k的递增序列。这种情况下，算法能够正确处理全元素相同的情况，确保了正确的逻辑判断。
是的，这里的逻辑充分考虑了包括数组只有一个元素在内的所有边界情况。当数组只有一个元素时，`cnt`初始化为1，表示数组中唯一的这一个元素。最后的检查`cnt * k <= n`用来确保即使是只有一个元素的数组也能正确处理。如果k大于1，则`cnt * k`会大于n，返回`False`；如果k等于1，检查条件满足，返回`True`。因此，算法在处理包括极端情况在内的所有场景时都是有效的。
选择更新`pre`和`cnt`的方法主要是因为这种方式在空间和时间效率上都较优。通过维护一个简单的计数器和前一个元素的值，我们可以在一次遍历中即时更新和检查每个元素的出现次数，而不需要额外的空间来存储每个元素的频率。使用字典或数组虽然可以更直观地存储每个元素的频率，但这会增加空间复杂度，并可能引入不必要的计算和存储开销。当前的实现方式提供了一种简洁且高效的解决方案。