Leetcode-1574.删除最短的子数组使剩余数组有序
Leetcode-1574.
题目：给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是非递减的。一个子数组指的是原数组中连续的一个子序列。请你返回满足题目要求的最短子数组的长度。
首先我们的思路是双指针，一个从头部开始，一个从尾部开始； 尾部的先往前找，找到开始递增的临界点记录下来；然后再依次与头部的指针相对比；
下面我们直接看代码以及注释：
代码语言：javascript复制 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;
}
