leetcode 3349. 检测相邻递增子数组 I 简单
·
给你一个由 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 <= 1001 <= 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;
}
更多推荐

所有评论(0)