3255. Find the Power of K-Size Subarrays II
Description
You are given an array of integers nums
of length n
and a positive integer k
.
The power of an array is defined as:
- Its maximum element if all of its elements are consecutive and sorted in ascending order.
- -1 otherwise.
You need to find the power of all subarrays of nums
of size k
.
Return an integer array results
of size n - k + 1
, where results[i]
is the power of nums[i..(i + k - 1)]
.
Example 1:
Input: nums = [1,2,3,4,3,2,5], k = 3
Output: [3,4,-1,-1,-1]
Explanation:
There are 5 subarrays of nums
of size 3:
[1, 2, 3]
with the maximum element 3.[2, 3, 4]
with the maximum element 4.[3, 4, 3]
whose elements are not consecutive.[4, 3, 2]
whose elements are not sorted.[3, 2, 5]
whose elements are not consecutive.
Example 2:
Input: nums = [2,2,2,2,2], k = 4
Output: [-1,-1]
Example 3:
Input: nums = [3,2,3,2,3,2], k = 2
Output: [-1,3,-1,3,-1]
Constraints:
1 <= n == nums.length <= 105
1 <= nums[i] <= 106
1 <= k <= n
Solutions
Solution 1: Recursion
We define an array $f$, where $f[i]$ represents the length of the continuous increasing subsequence ending at the $i$-th element. Initially, $f[i] = 1$.
Next, we traverse the array $\textit{nums}$ to calculate the values of the array $f$. If $nums[i] = nums[i - 1] + 1$, then $f[i] = f[i - 1] + 1$; otherwise, $f[i] = 1$.
Then, we traverse the array $f$ in the range $[k - 1, n)$. If $f[i] \ge k$, we add $\textit{nums}[i]$ to the answer array; otherwise, we add $-1$.
After the traversal, we return the answer array.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ represents the length of the array $\textit{nums}$.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 |