What is the core pattern used in Find the Power of K-Size Subarrays II?

The problem relies on a sliding window with running state updates to compute subarray powers without recomputing each window.

Can this algorithm handle repeated elements correctly?

Yes, careful state tracking ensures that repeated numbers disrupting sequences are handled while computing the power.

What is the time complexity of the recommended solution?

The solution runs in O(n) time because each element is added and removed from the sliding window once while maintaining the state.

How should edge cases like k = 1 be handled?

For k = 1, each element forms a subarray of size 1, so the power is determined directly from the element itself without window comparison.

Is it necessary to store auxiliary state for sequences?

Yes, auxiliary state is required to track consecutive increasing sequences efficiently as the window slides and prevents recalculating full subarrays.

#3255

Medium

auto_awesome滑动窗口（状态滚动更新）

LeetCode 题解工作台

长度为 K 的子数组的能量值 II

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。一个数组的能量值定义为：如果所有元素都是依次连续（即 nums[i] + 1 = nums[i + 1] ， i ）且上升的，那么能量值为最大的元素。否则为 -1 。你需要求出 nums 中所有长度为 k 的 …

数组滑动窗口

题目描述

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

如果所有元素都是依次连续（即 nums[i] + 1 = nums[i + 1]，i < n）且上升的，那么能量值为最大的元素。
否则为 -1 。

你需要求出 nums 中所有长度为 k 的子数组的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i..(i + k - 1)] 的能量值。

示例 1：

输入：nums = [1,2,3,4,3,2,5], k = 3

输出：[3,4,-1,-1,-1]

解释：

nums 中总共有 5 个长度为 3 的子数组：

[1, 2, 3] 中最大元素为 3 。
[2, 3, 4] 中最大元素为 4 。
[3, 4, 3] 中元素不是连续的。
[4, 3, 2] 中元素不是上升的。
[3, 2, 5] 中元素不是连续的。

示例 2：

输入：nums = [2,2,2,2,2], k = 4

输出：[-1,-1]

示例 3：

输入：nums = [3,2,3,2,3,2], k = 2

输出：[-1,3,-1,3,-1]

提示：

1 <= n == nums.length <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= n

lightbulb

解题思路

方法一：递推

我们定义一个数组 $f$ ，其中 $f[i]$ 表示以第 $i$ 个元素结尾的连续上升子序列的长度。初始时 $f[i] = 1$ 。

接下来，我们遍历数组 $\textit{nums}$ ，计算数组 $f$ 的值。如果 $nums[i] = nums[i - 1] + 1$ ，则 $f[i] = f[i - 1] + 1$ ；否则 $f[i] = 1$ 。

然后，我们在 $[k - 1, n)$ 的范围内遍历数组 $f$ ，如果 $f[i] \ge k$ ，那么答案数组添加 $\textit{nums}$ ，否则添加 $-1$ 。

遍历结束后，返回答案数组。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 表示数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        f = [1] * n
        for i in range(1, n):
            if nums[i] == nums[i - 1] + 1:
                f[i] = f[i - 1] + 1
        return [nums[i] if f[i] >= k else -1 for i in range(k - 1, n)]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect optimized O(n) solution using sliding window with running state updates.
question_mark
Look for careful handling of sequences that break consecutiveness within windows.
question_mark
Assess if edge cases with repeated numbers or k = 1 are correctly handled.

warning

常见陷阱

外企场景

error
Recomputing the entire window's power from scratch on each slide leading to O(n*k) time.
error
Failing to update state correctly when the outgoing element affects the consecutive sequence.
error
Incorrectly handling repeated numbers that disrupt the consecutive order in a subarray.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the sum of powers instead of individual subarray powers.
arrow_right_alt
Find the maximum power across all k-size subarrays instead of returning the array.
arrow_right_alt
Extend the problem to variable-size windows and track the longest consecutive sequence for each size.

help

常见问题

外企场景

继续练习

#3254 长度为 K 的子数组的能量值 I #3261 统计满足 K 约束的子字符串数量 II #3208 交替组 II