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]
解释：
有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

解题思路

这道题要求找到所有长度为k的子数组的"幂"，需要判断子数组是否为连续递增序列。

核心思路：

  1. 一个数组是连续递增序列，当且仅当相邻元素差值都为1
  2. 可以用动态规划预处理：dp[i] 表示以位置i结尾的最长连续递增序列长度
  3. 对于每个长度为k的子数组，如果 dp[i] >= k，说明该子数组是连续递增的

优化方法：

  • 方法一：使用dp数组预处理 + 滑动窗口，时间复杂度O(n)
  • 方法二：直接滑动窗口维护连续长度，空间更优

实现细节：

  • dp[i] 初始化为1（单个元素自成连续序列）
  • 如果 nums[i] == nums[i-1] + 1，则 dp[i] = dp[i-1] + 1
  • 检查每个子数组时，只需要看结尾位置的dp值是否≥k

推荐使用方法一，代码简洁且易理解。

代码实现

class Solution {
public:
    vector<int> resultsArray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> dp(n, 1);
        
        // 预处理：计算以每个位置结尾的最长连续递增序列长度
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[i-1] + 1) {
                dp[i] = dp[i-1] + 1;
            }
        }
        
        vector<int> result(n - k + 1);
        for (int i = k - 1; i < n; i++) {
            if (dp[i] >= k) {
                result[i - k + 1] = nums[i];
            } else {
                result[i - k + 1] = -1;
            }
        }
        
        return result;
    }
};

class Solution:
    def resultsArray(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        dp = [1] * n
        
        # 预处理：计算以每个位置结尾的最长连续递增序列长度
        for i in range(1, n):
            if nums[i] == nums[i-1] + 1:
                dp[i] = dp[i-1] + 1
        
        result = []
        for i in range(k-1, n):
            if dp[i] >= k:
                result.append(nums[i])
            else:
                result.append(-1)
        
        return result

public class Solution {
    public int[] ResultsArray(int[] nums, int k) {
        int n = nums.Length;
        int[] dp = new int[n];
        Array.Fill(dp, 1);
        
        // 预处理：计算以每个位置结尾的最长连续递增序列长度
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[i-1] + 1) {
                dp[i] = dp[i-1] + 1;
            }
        }
        
        int[] result = new int[n - k + 1];
        for (int i = k - 1; i < n; i++) {
            if (dp[i] >= k) {
                result[i - k + 1] = nums[i];
            } else {
                result[i - k + 1] = -1;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var resultsArray = function(nums, k) {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    
    // 预处理：计算以每个位置结尾的最长连续递增序列长度
    for (let i = 1; i < n; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

其中n为数组长度。算法只需要遍历数组两次，时间复杂度为线性。空间复杂度主要用于存储dp数组和结果数组。

相关题目