题解：3254. 长度为 K 的子数组的能量值

Problem: 3254. 长度为 K 的子数组的能量值 I

题解：3254. 长度为 K 的子数组的能量值

给定一个数组 nums 和一个整数 k，我们需要找出所有长度为 k 的子数组的“能量值”。根据题意：

• 如果子数组是连续递增的，能量值等于子数组中的最大元素。
• 否则，能量值为 -1。

以下是两种不同的解法。第一种是暴力法，第二种是使用滑动窗口法进行优化。

方法一：暴力法

思路

遍历每一个长度为 k 的子数组，逐个检查是否满足递增条件。若满足，则记录该子数组的最大值；否则记录 -1。

代码实现

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans(n - k + 1, -1); // 初始化结果数组，默认为-1

        // 遍历每一个长度为k的子数组
        for (int i = 0; i <= n - k; i++) {
            bool valid = true; // 标记该子数组是否连续递增

            // 检查当前子数组是否连续递增
            for (int j = i + 1; j < i + k; j++) {
                if (nums[j] - nums[j - 1] != 1) { // 不是连续递增
                    valid = false;
                    break;
                }
            }

            // 如果是递增的，记录最大值（即该子数组的最后一个元素）
            if (valid) {
                ans[i] = nums[i + k - 1];
            }
        }

        return ans;
    }
};

代码解释

1. 初始化 ans 数组，默认所有值为 -1。
2. 对于每个长度为 k 的子数组，从索引 i 到 i + k - 1：
   • 检查相邻元素是否连续递增。
   • 若所有相邻元素递增，则将该子数组的最后一个元素作为能量值。
3. 返回结果数组。

时间复杂度

• 时间复杂度：O(n * k)。对于每个长度为 k 的子数组，我们逐个检查是否递增。
• 空间复杂度：O(n - k + 1)。

方法二：滑动窗口法

思路

通过滑动窗口法优化。用指针 left 记录上一个非递增的起始位置，从而避免重复检查整个子数组。

代码实现

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n = nums.size();
        if (k == 1) { // 如果k=1，每个元素本身都是一个递增子数组
            return nums;
        }

        vector<int> ans(n - k + 1, -1); // 初始化结果数组，默认为-1
        int left = 0; // 标记递增子数组的起点

        // 从第二个元素开始遍历
        for (int i = 1; i < n; i++) {
            // 如果当前元素与前一个元素不连续递增，更新left
            if (nums[i] - nums[i - 1] != 1) {
                left = i;
            }

            // 检查是否形成长度为k的递增子数组
            if (i - left < k - 1) continue; // 当前子数组长度不够

            // 满足长度为k的递增子数组，记录最大值
            ans[left] = nums[i];

            // 滑动窗口右移，继续检查下一个子数组
            left++;
        }

        return ans;
    }
};

代码解释

1. 若 k = 1，每个元素单独成为一个子数组，直接返回 nums。
2. 初始化 left 为 0，表示递增子数组的开始位置。
3. 遍历数组，检查每个 nums[i]：
   • 如果 nums[i] - nums[i-1] != 1，则 nums[i] 和前一个元素不连续，更新 left = i。
   • 若 i - left 达到 k-1，则从 left 到 i 形成长度为 k 的递增子数组，记录 nums[i] 为能量值。
4. 将 left 右移继续检查。

时间复杂度

• 时间复杂度：O(n)，每个元素仅需一次遍历。
• 空间复杂度：O(n - k + 1)。