给你一个由 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

分析:用一个 flag 数组标记当前下标的子数组是否是严格递增的,再检查是否存在相邻子数组是否都是严格递增的即可。

bool hasIncreasingSubarrays(int* nums, int numsSize, int k) {
    int flag[numsSize+5];
    if(k==1)return true;k--;
    for(int i=0;i<numsSize;++i)
        flag[i]=0;
    for(int i=0;i<numsSize-k;++i)
    {
        if(!i||!flag[i-1])
        {
            int f=1,idx=i;
            for(int j=i+1,t=0;t<k&&f;++t,++j)
            {
                if(nums[j]<=nums[j-1])
                {
                    f=0,idx=j;
                }
            }
            if(f)flag[i]=1;
            else
            {
                for(int j=i;j<idx;++j)
                    flag[j]=0;
                i=idx-1;
            }
        }
        else
        {
            if(nums[i+k]>nums[i+k-1])flag[i]=1;
            else
            {
                for(int j=i,t=0;t<k;++t,++j)
                    flag[j]=0;
                i=i+k-1;
            }
        }
    }
    // for(int i=0;i<numsSize;++i)
    //     printf("i=%d flag=%d\n",i,flag[i]);
    for(int i=0;i+k+1<numsSize;++i)
    {
        // printf("i=%d flag1=%d flag2=%d\n",i,flag[i],flag[i+k+1]);
        if(flag[i]&&flag[i+k+1])return true;
    }
        
    return false;
}

更多推荐