题目描述

给你一个由 n 个整数组成的数组 nums 和一个整数 k，请你确定是否存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：

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

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

子数组 是数组中的一个连续 非空 的元素序列。

样例

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

输出：true

解释：

从下标 2 开始的子数组为 [7, 8, 9]，它是严格递增的。
从下标 5 开始的子数组为 [2, 3, 4]，它也是严格递增的。
两个子数组是相邻的，因此结果为 true。

输入：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

算法

(遍历) $O(n)$

1. 遍历数组，遍历时记录当前连续最长上升的长度，以及布尔变量 $seen$ 表示上一次连续最长上升的长度是否大于等于 $k$。
2. 如果遇到非递增的情况，如果当前连续最长上升的长度大于等于 $2k$，则返回 $true$；如果当前连续最长上升的长度小于 $k$，则令 $seen$ 为 $false$；如果当前连续最长上升的长度大于等于 $k$，且 $seen$ 为 $true$，则返回 $true$，否则令 $seen$ 为 $true$。

时间复杂度

• 遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    bool hasIncreasingSubarrays(vector<int>& nums, int k) {
        const int n = nums.size();

        bool seen = false;
        int incr = 1;
        for (int i = 0; i < n; i++) {
            if (i < n - 1 && nums[i + 1] > nums[i]) {
                ++incr;
            } else {
                if (incr >= 2 * k)
                    return true;

                if (incr < k) {
                    seen = false;
                } else {
                    if (seen)
                        return true;

                    seen = true;
                }

                incr = 1;
            }
        }

        return false;
    }
};