Leetcode-1574.删除最短的子数组使剩余数组有序
Leetcode-1574.
题目：给你一个整数数组 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; }
