Leetcode 3255. Find the Power of K-Size Subarrays II

• Leetcode 3255. Find the Power of K-Size Subarrays II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3255. Find the Power of K-Size Subarrays II

1. 解题思路

这一题是题目3254的进阶版，其实主要就是增加了算法复杂度。

整体上来说的话思路还是一个分段的思路，我们找到所有的满足条件的连续递增数列，显然他们之间不可能有交集。

然后，对于任何一个连续递增的数列，假设其长度为$m$，如果$m<k$，那显然无法构成长度不少于$k$的数组，因此我们返回一个长度为$m$的$-1$的数组即可，反之如果$m\ge k$，那么其返回结果的前$k-1$个值就是$-1$，后面则就是原始数组当中的值了。

我们将所有数组拼凑在一起，然后去除掉前$k-1$个元素即为我们最终的解答了。

2. 代码实现

给出python代码实现如下：

class Solution:def resultsArray(self, nums: List[int], k: int) -> List[int]:n = len(nums)i = 0ans = []while i < n:j = iwhile j < n-1 and nums[j+1] == nums[j]+1:j += 1m = j-i+1if m >= k:ans += [-1] * (k-1) + nums[i+k-1:j+1]else:ans += [-1] * mi = j+1return ans[k-1:]

提交代码评测得到：耗时1312ms，占用内存32.9MB。