题目:给你一个整数数组 arr ,请你删除一个子数组(可以为空),使得 arr 中剩下的元素是非递减的。一个子数组指的是原数组中连续的一个子序列。请你返回满足题目要求的最短子数组的长度。
首先我们的思路是双指针,一个从头部开始,一个从尾部开始; 尾部的先往前找,找到开始递增的临界点记录下来;然后再依次与头部的指针相对比;
下面我们直接看代码以及注释:
int findLengthOfShortestSubarray(int* arr, int arrSize)
{
int j = arrSize - 1;
//j从尾部开始往前找(尾部往前是递减的),找到开始递增的的临界点的下标j
//注意这里j>0要放在arr[j - 1] <= arr[j]的前面,不然Leetcode过不了
while (j > 0 && arr[j - 1] <= arr[j])
{
j--;
}
if (j == 0)
{
return 0;
}
//将j的下标赋给len,现在代表从下标0开始到j相差的长度为len
int len = j;
//j从len的位置开始
//i从前面开始往后走(从前往后走是递增的),i每走一步,更新len的长度j-i-1;
//因为len会记录i上一次所在元素时与j相差的长度,理论上arr[i] <= arr[j] ,满足这个条件时有可能记录的这个长度就是题目所求,
//但是为了求最优解,i还需要往后走,当 arr[i] > arr[j] 时j也往后走,直到满足arr[i] <= arr[j],继续记录这时的长度;
for (int i = 0; i < arrSize; i++)
{
while (j < arrSize && arr[i] > arr[j])
{
j++;
}
//更新长度
if ((j - i - 1) < len)
{
len = j - i - 1;
}
//在记录长度的同时,也要保证arr[i] > arr[i + 1]并且数组不越界,如果不满足条件,直接跳出循环,返回的这个len值就是最优解
if (arr[i] > arr[i + 1] && i + 1 < arrSize)
{
break;
}
}
return len;
}