目标
给你一个长度为 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 <= 500
- 1 <= nums[i] <= 10^5
- 1 <= k <= n
思路
有一个整数数组 nums，如果其子数组中的元素是连续且递增的，即公差为 1 的数列，定义子数组的能量值为子数组的最大元素，否则能量为 -1。返回所有长度为 k 的子数组的能量值。
显然需要使用滑动窗口，关键在于元素移入移出后如何判断是否连续且递增。我们可以使用队列记录不满足规则元素的 前一个 元素下标。当元素移入窗口时，判断元素与前一个元素是否满足规则，不满足则将前一个元素下标加入队列。窗口滑动时，先判断被移出的元素下标是否与队首相同，如果相同将队首元素删除。最后判断队列是否为空，如果为空则能量为新加入的元素，否则为 -1。
官网题解使用一个计数器记录连续递增的元素个数，初始化结果数组元素为 -1，当计数器大于等于 k 时，记录 i - k + 1 位置上的能量值为当前元素，否则将计数器重置为 1。
代码
/**
* @date 2024-11-06 5:50
*/
public class ResultsArray3254 {
public int[] resultsArray(int[] nums, int k) {
int n = nums.length;
if (k == 1) {
return nums;
}
int[] res = new int[n - k + 1];
Queue<Integer> q = new ArrayDeque<>();
int l = 0, i = 0;
for (int r = 1; r < n; r++) {
int prev = r - 1;
if (nums[r] - nums[prev] != 1) {
q.offer(prev);
}
if (r - l + 1 > k) {
if (!q.isEmpty() && l == q.peek()) {
q.poll();
}
l++;
}
if (r - l + 1 == k) {
if (q.isEmpty()) {
res[i++] = nums[r];
} else {
res[i++] = -1;
}
}
}
return res;
}
}
性能
