1单调性
- 应用场景：常应用于双指针的进一步优化问题中
- 含义：针对指针 i 1 > i i1>i i1>i一定有 j 1 > = j j1>=j j1>=j或者 j 1 < = j j1<=j j1<=j
- 这样我们就可以利用该性质对算法进行进一步优化，避免一些不必要的遍历
2. leetcode题目举例
思路分析
假设删除的是 a r r [ i + 1 ] ∼ a r r [ j − 1 ] arr[i+1]∼arr[j−1] arr[i+1]∼arr[j−1]则需要满足以下条件
- a r r [ 0 ] ∼ a r r [ i ] arr[0]∼arr[i] arr[0]∼arr[i]非递减。
- a r r [ j ] ∼ a r r [ n − 1 ] arr[j]∼arr[n−1] arr[j]∼arr[n−1]非递减
- a r r [ i ] ≤ a r r [ j ] arr[i]≤arr[j] arr[i]≤arr[j]
如果我们对所有满足条件的 i i i 和 j j j进行一次二次遍历，则时间复杂度为O（lr）其中 l 为左半部分长度，r为右半部分长度- 我们尝试去寻找 i i i和 j j j的规律
- 对于 左半部分的 x ( 左半部分非递减段 ) x(左半部分非递减段) x(左半部分非递减段) 我们假设 最小的 符合条件的 j j j为 y y y
- 如果有 x 1 > x x1>x x1>x,则至少有 y 1 > = y y1>=y y1>=y（优化的重要性质）
证明(反证法)
- 如果 y 1 < y y1<y y1<y
则又因为- x 1 > x x1>x x1>x
- a r r [ y 1 ] > = a r r [ x 1 ] arr[y1]>=arr[x1] arr[y1]>=arr[x1],
- a r r [ x 1 ] > = a r r [ x ] arr[x1]>=arr[x] arr[x1]>=arr[x]
所以 a r r [ y 1 ] > = a r r [ x ] arr[y1]>=arr[x] arr[y1]>=arr[x] 且， x , y 1 ， y x,y1， y x,y1，y 位于左右部分的非递减段，则 y 1 y1 y1 为 x x x 对应的最小答案，与先前定义不符举例说明
我们以题中示例举例 （这里我们直接时候对应的值，括号中为下标，方便理解）
- [1,2,3,10,4,2,3,5]
- 1(0) 对应的最小的 j 为 为2（5）
- 我们遍历 2（1）对应的 j 最小为 2(5) ,不可能在2（5）的前面寻找
- 这就是我们所证明的性质的意思
class Solution {
//单调性
//对于任意的 i1>i
//其对应的j 一定有 j1>=j
public int findLengthOfShortestSubarray(int[] nums) {
int n=nums.length;
int j=n-1;
//寻找最靠左的j
while(j>=1 && nums[j]>=nums[j-1])j--;
//J 为0说明本身就是非递减，无需删除
if(j==0)return 0;
//最长的删除长度，前半部分全部删除
int res=j;
//枚举 i
for(int i=0;i<n;){
//寻找最小的符合条件的 j
while(j<n && nums[i]>nums[j])j++;
res=Math.min(res,j-i-1);
//如果 i 还在非递减段则枚举下一个，否则，停止枚举
if(i!=n-1 &&nums[i+1]>=nums[i])i++;
else break;
}
return res;
}
}
