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

#python #leetcode #sliding-window #deque

题目描述

关联：

• https://leetcode.cn/problems/find-the-power-of-k-size-subarrays-i/description/
• https://leetcode.cn/problems/find-the-power-of-k-size-subarrays-ii/description/ （3255）

题目描述

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

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

• 如果 所有 元素都是依次 连续 且 上升 的，那么能量值为 最大 的元素。
• 否则为 -1。

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

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

本题和 3254. 长度为 K 的子数组的能量值 I 的区别在于，本题的数据量更大。

\(1 \leq n = \text{nums.length}\leq 10^5\)

\(1 \leq \text{nums}[i] \leq 10^5\)

\(1 \leq k \leq n\)

完整题解

3254. 长度为 K 的子数组的能量值 I 的题解依旧可以用于本题，并且时间上还不错。

from collections import deque

class Solution:
    def resultsArray(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        results = []
        invalid = deque()

        if k == 1:
            return nums

        for i in range(n - 1):
            if nums[i] + 1 != nums[i + 1]:
                invalid.append(i)

        i = 0
        while i <= n - k:  # [0..k] ~ [n-k..n]

            if not invalid or i + k - 1 <= invalid[0]:
                results.append(nums[i + k - 1])
                i += 1

            else:
                next_start = invalid.popleft() + 1
                # 跳过了几个值，就添加几个 -1，跳过的时候要随时检查右边界 i + k 不能超过 n
                while i < next_start and i <= n - k:  
                    results.append(-1)
                    i += 1
                i = next_start

        return results

复杂度分析

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。

评论