Easy

题目描述

给定一个由 n 个整数组成的数组 nums 和一个整数 k，判断是否存在两个相邻的长度为 k 的子数组，使得这两个子数组都是严格递增的。具体来说，检查是否存在两个起始索引为 a 和 b (a < b) 的子数组，其中：

  • 两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是严格递增的。
  • 这两个子数组必须是相邻的，意味着 b = a + k。

如果可以找到两个这样的子数组，返回 true，否则返回 false。

示例 1：

输入：nums = [2,5,7,8,9,2,3,4,3,1], k = 3

输出：true

解释：

  • 从索引 2 开始的子数组是 [7, 8, 9]，严格递增。
  • 从索引 5 开始的子数组是 [2, 3, 4]，也是严格递增。
  • 这两个子数组相邻，所以结果是 true。

示例 2：

输入：nums = [1,2,3,4,4,4,4,5,6,7], k = 5

输出：false

约束条件：

  • 2 <= nums.length <= 100
  • 1 < 2 * k <= nums.length
  • -1000 <= nums[i] <= 1000

提示：

  • 存储在某个索引处开始和结束的最长递减子数组。

解题思路

解题思路

这道题要求找到两个相邻的长度为 k 的严格递增子数组。我们可以通过以下步骤来解决：

方法一：直接遍历检查（推荐）

  1. 遍历可能的起始位置：对于每个可能的起始位置 i（满足 i + 2*k - 1 < n），检查从 i 开始的两个长度为 k 的相邻子数组。

  2. 检查严格递增：对于每个子数组，检查是否所有相邻元素都满足 nums[j] < nums[j+1]。

  3. 相邻条件：第二个子数组的起始位置应该是 i + k，这样两个子数组就是相邻的。

方法二：预处理递增长度

我们还可以预处理每个位置开始的最长递增子数组长度，然后检查是否存在某个位置 i，使得从 i 开始和从 i+k 开始的递增长度都至少为 k。

时间复杂度方面，由于数组长度最多 100，k 最大 50，直接遍历的方法已经足够高效。代码实现上，方法一更加直观易懂。

代码实现

class Solution {
public:
    bool hasIncreasingSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        
        // 检查从位置i开始长度为k的子数组是否严格递增
        auto isIncreasing = [&](int start) -> bool {
            for (int i = start; i < start + k - 1; i++) {
                if (nums[i] >= nums[i + 1]) {
                    return false;
                }
            }
            return true;
        };
        
        // 遍历所有可能的起始位置
        for (int i = 0; i <= n - 2 * k; i++) {
            if (isIncreasing(i) && isIncreasing(i + k)) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def hasIncreasingSubarrays(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        
        def is_increasing(start):
            for i in range(start, start + k - 1):
                if nums[i] >= nums[i + 1]:
                    return False
            return True
        
        # 遍历所有可能的起始位置
        for i in range(n - 2 * k + 1):
            if is_increasing(i) and is_increasing(i + k):
                return True
        
        return False

public class Solution {
    public bool HasIncreasingSubarrays(IList<int> nums, int k) {
        int n = nums.Count;
        
        bool IsIncreasing(int start) {
            for (int i = start; i < start + k - 1; i++) {
                if (nums[i] >= nums[i + 1]) {
                    return false;
                }
            }
            return true;
        }
        
        // 遍历所有可能的起始位置
        for (int i = 0; i <= n - 2 * k; i++) {
            if (IsIncreasing(i) && IsIncreasing(i + k)) {
                return true;
            }
        }
        
        return false;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var hasIncreasingSubarrays = function(nums, k) {
    const n = nums.length;
    
    const isIncreasing = (start) => {
        for (let i = start; i < start + k - 1; i++) {
            if (nums[i] >= nums[i + 1]) {
                return false;
            }
        }
        return true;
    };
    
    // 遍历所有可能的起始位置
    for (let i = 0; i <= n - 2 * k; i++) {
        if (isIncreasing(i) && isIncreasing(i + k)) {
            return true;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值
时间复杂度O(n × k)
空间复杂度O(1)

说明：

  • 时间复杂度：我们需要遍历 O(n) 个可能的起始位置，对于每个位置需要检查两个长度为 k 的子数组是否递增，每次检查需要 O(k) 时间。
  • 空间复杂度：只使用了常数额外空间。