Medium

题目描述

给你一个长度为 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

解题思路

这道题需要判断每个长度为 k 的子数组是否满足"连续且升序"的条件。

解题思路

方法一：暴力解法

  • 对于每个起始位置 i，检查子数组 nums[i..i+k-1]
  • 验证相邻元素是否连续（差值为1）且升序
  • 如果满足条件，返回最大值（即最后一个元素）；否则返回 -1
  • 时间复杂度 O(n*k)，适合题目约束条件

方法二：滑动窗口优化

  • 预处理：计算每个位置开始的连续递增序列长度
  • 使用滑动窗口，如果当前窗口的连续长度 >= k，则满足条件
  • 时间复杂度 O(n)，空间复杂度 O(n)

由于题目约束 n ≤ 500，两种方法都可行。这里推荐方法一，代码简洁易懂。

核心逻辑：

  1. 遍历所有可能的起始位置
  2. 对每个子数组，检查是否严格递增且连续
  3. 连续意味着 nums[j] = nums[j-1] + 1
  4. 如果整个子数组满足条件，最大值就是最后一个元素

代码实现

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> results(n - k + 1);
        
        for (int i = 0; i <= n - k; i++) {
            bool isValid = true;
            for (int j = i + 1; j < i + k; j++) {
                if (nums[j] != nums[j - 1] + 1) {
                    isValid = false;
                    break;
                }
            }
            results[i] = isValid ? nums[i + k - 1] : -1;
        }
        
        return results;
    }
};

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        results = []
        
        for i in range(n - k + 1):
            is_valid = True
            for j in range(i + 1, i + k):
                if nums[j] != nums[j - 1] + 1:
                    is_valid = False
                    break
            
            if is_valid:
                results.append(nums[i + k - 1])
            else:
                results.append(-1)
        
        return results

public class Solution {
    public int[] ResultsArray(int[] nums, int k) {
        int n = nums.Length;
        int[] results = new int[n - k + 1];
        
        for (int i = 0; i <= n - k; i++) {
            bool isValid = true;
            for (int j = i + 1; j < i + k; j++) {
                if (nums[j] != nums[j - 1] + 1) {
                    isValid = false;
                    break;
                }
            }
            results[i] = isValid ? nums[i + k - 1] : -1;
        }
        
        return results;
    }
}

var resultsArray = function(nums, k) {
    const n = nums.length;
    const results = [];
    
    for (let i = 0; i <= n - k; i++) {
        let isValid = true;
        for (let j = i + 1; j < i + k; j++) {
            if (nums[j] !== nums[j - 1] + 1) {
                isValid = false;
                break;
            }
        }
        results.push(isValid ? nums[i + k - 1] : -1);
    }
    
    return results;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度暴力解法滑动窗口优化
时间复杂度O(n × k)O(n)
空间复杂度O(1)O(n)

说明：

  • n 为数组长度
  • 暴力解法：对每个子数组都需要 O(k) 时间验证，共有 O(n) 个子数组
  • 滑动窗口：预处理 O(n)，查询 O(1)
  • 由于题目约束 n ≤ 500，暴力解法完全够用且代码更简洁

相关题目