3254. Find the Power of K-Size Subarrays I

Problem

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.

A subarray is a contiguous non-empty sequence of elements within an array.

Return an integer array results of size n - k + 1, where results[i] is the power of nums[i..(i + k - 1)].

https://leetcode.cn/problems/find-the-power-of-k-size-subarrays-i/

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 <= 500
1 <= nums[i] <= 10⁵
1 <= k <= n

Test Cases

1 2	class Solution: def resultsArray(self, nums: List[int], k: int) -> List[int]:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, k, expected', [
    ([1,2,3,4,3,2,5], 3, [3,4,-1,-1,-1]),
    ([2,2,2,2,2], 4, [-1,-1]),
    ([3,2,3,2,3,2], 2, [-1,3,-1,3,-1]),

    ([1], 1, [1]),
    ([6], 1, [6]),
])
class Test:
    def test_solution(self, nums, k, expected):
        sol = Solution()
        assert sol.resultsArray(nums, k) == expected

Thoughts

跟 3208. Alternating Groups II 基本是同一个问题，只是数组首尾不再相接，连续条件从颜色交替变为 +1 递增。直接在其代码基础上修改一下就行了。

时间复杂度 O(n)（没有首尾相接，所以不需要 O(n + k)）。

Code

solution.py

class Solution:
    def resultsArray(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        powers = [-1] * (n - k + 1)
        length = 0
        for i in range(0, n):
            if i == 0 or nums[i] != nums[i-1] + 1:
                length = 1
            elif length < k:
                length += 1

            if length == k:
                powers[i - k + 1] = nums[i]
        return powers