LeetCode 3255.长度为 K 的子数组的能量值 II：和官解思路不同的O(n)做法（附思考过程）

【LetMeFly】3255.长度为 K 的子数组的能量值 II：和官解思路不同的O(n)做法（附思考过程）

力扣题目链接：https://leetcode.cn/problems/find-the-power-of-k-size-subarrays-ii/

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

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

如果所有元素都是依次连续且上升的，那么能量值为最大的元素。
否则为 -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

解题方法：遍历（类似滑动窗口）

本题长度为 K 的子数组的能量值 II和上一题长度为 K 的子数组的能量值 I的唯一区别是数据量，本题数据量不支持 $O (nk)$ 时间复杂度的做法。

上一题中我们枚举每个长度为K的区间的左端点，之后遍历区间，若区间中存在“相邻不连续”的两个元素则能量值为-1，否则为区间的最后一个元素。每个区间都可能需要 $O (k)$ 的时间复杂度来完成结果的计算。

但是其实不难发现，区间（假设k很大区间很长）每次向右移动一个元素，区间中大量的元素是不变的，只有区间起始位置元素和结束位置元素发生了变化。

因此解决方案来了，我们使用一个额外的变量 $n o tC o n t in u e$ 记录区间中不连续的“相邻两个元素”有多少对，这样在区间移动的时候只需要根据区间开头元素和末尾元素的变化情况就能在 $O (1)$ 的时间内算出新区间的“notContinue”。

如果一个区间的 $n o tC o u t in u e$ 非零，则说明该区间中存在相邻不连续的元素对，区间“能量值”为 $- 1$ ；否则区间能量值为区间的最后一个元素（即最大元素）。

时间复杂度 $O (n)$
空间复杂度 $O (1)$ ，力扣返回值不计入算法空间复杂度

AC代码

C++

class Solution {
public:vector<int> resultsArray(vector<int>& nums, int k) {vector<int> ans(nums.size() - k + 1);int notContinue = 0;for (int i = 1; i < k; i++) {notContinue += nums[i] != nums[i - 1] + 1;}ans[0] = notContinue ? -1 : nums[k - 1];for (int i = 1; i + k <= nums.size(); i++) {notContinue -= nums[i] != nums[i - 1] + 1;notContinue += nums[i + k - 1] != nums[i + k - 2] + 1;ans[i] = notContinue ? -1 : nums[i + k - 1];}return ans;}
};

Python

from typing import Listclass Solution:def resultsArray(self, nums: List[int], k: int) -> List[int]:ans = [0] * (len(nums) - k + 1)notCoutinue = sum(nums[i] != nums[i -  1] + 1 for i in range(1, k))ans[0] = -1 if notCoutinue else nums[k - 1]for i in range(1, len(nums) - k + 1):notCoutinue -= nums[i] != nums[i - 1] + 1notCoutinue += nums[i + k - 1] != nums[i + k - 2] + 1ans[i] = -1 if notCoutinue else nums[i + k - 1]return ans

Java

class Solution {public int[] resultsArray(int[] nums, int k) {int[] ans = new int[nums.length - k + 1];int notCoutinue = 0;for (int i = 1; i < k; i++) {if (nums[i] != nums[i - 1] + 1) {notCoutinue++;}}ans[0] = notCoutinue > 0 ? -1 : nums[k - 1];for (int i = 1; i + k <= nums.length; i++) {if (nums[i] != nums[i - 1] + 1) {notCoutinue--;}if (nums[i + k - 1] != nums[i + k - 2] + 1) {notCoutinue++;}ans[i] = notCoutinue > 0 ? -1 : nums[i + k - 1];}return ans;}
}

Go

package mainfunc resultsArray(nums []int, k int) (ans []int) {ans = make([]int, len(nums) - k + 1)notContinue := 0for i := 1; i < k; i++ {if nums[i] != nums[i - 1] + 1 {notContinue++}}if notContinue > 0 {ans[0] = -1} else {ans[0] = nums[k - 1]}for i := 1; i + k <= len(nums); i++ {if nums[i] != nums[i - 1] + 1 {notContinue--}if nums[i + k - 1] != nums[i + k - 2] + 1 {notContinue++}if notContinue > 0 {ans[i] = -1} else {ans[i] = nums[i + k - 1]}}return
}