目标
给你一个长度为 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^5
- 1 <= nums[i] <= 10^6
- 1 <= k <= n
思路
有一个整数数组 nums，如果其子数组中的元素是连续且递增的，即公差为 1 的数列，定义子数组的能量值为子数组的最大元素，否则能量为 -1。返回所有长度为 k 的子数组的能量值。
与 3254.长度为K的子数组的能量值I 相比，数据范围从 1 ~ 500 变成了 1 ~ 10^5。数据范围小可以枚举长度为 k 的子数组，时间复杂度为 O((n - k + 1) * k)，即起点个数 * 子数组长度。
对于这个题，如果 n 取 10^5，k 取 10^4， n - k 是 9 * 10^8 复杂度接近 10^9 超时。
今天换一个解法，记录连续递增的个数。
代码
/**
* @date 2024-11-07 8:41
*/
public class ResultsArray3255 {
public int[] resultsArray(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
Arrays.fill(res, -1);
int cnt = 1;
for (int i = 0; i < n; i++) {
if (i == 0 || nums[i] - nums[i - 1] != 1) {
cnt = 1;
} else {
cnt++;
}
if (cnt >= k) {
res[i - k + 1] = nums[i];
}
}
return res;
}
}
性能
