高校校园网站建设评比自评/福州网站建设

1574. 删除最短的子数组使剩余数组有序

目录

1、双指针+二分 

2、双指针

题目：

给你一个数组a ，请你删除一个子数组（可以为空），使 a中剩下的元素是非递减的

一个子数组指的是原数组中连续的一个子序列

请你返回满足题目要求的最短子数组的长度

1、双指针+二分 

思路：

刚开始没动脑子，上来一个反向最长上升子序列直接wa

错误原因是：最长上升子序列选的是跳着选的，如果这么解部分样例会出现删除两个及以上的子数组，而题目要求删除一个连续子数组，所以dp是不对的

• 先找出数组两端的最长非递减前缀和最长非递减后缀
• res=min(删前缀，删后缀）
• 枚举前缀的每一个点l作为最右端点
• 对于每个l，二分找出在后缀里第一个≥arr[l]的下标r
• 更新答案res=min(res,r-l-1)

class Solution {public int findLengthOfShortestSubarray(int[] arr) {int n=arr.length;//先找出数组两端的最长非递减前缀和最长非递减后缀int l=0,r=n-1;while(l+1<n&&arr[l]<=arr[l+1]) l++;while(r-1>=0&&arr[r]>=arr[r-1]) r--;if(l>=r) return 0; //如果最长非递减前后缀重叠 说明整个序列都是非递减int res=Math.min(r,n-1-l); //res=min(删前缀，删后缀)//枚举前缀的每一个点l作为最右端点//对于每个l，二分找出在后缀里第一个≥arr[l]的下标r//更新答案res=min(res,r-l-1)，最短子数组就是区间[l+1,r-1] r-1-l-1+1=r-l-1for(int i=0;i<=l;i++){int rr=search(arr,arr[i],r);res=Math.min(res,rr-i-1);}return res;}public int search(int[] arr,int target,int l){int r=arr.length; //这里多设置1 是因为如果后缀中找不到≥arr[l]的数时 则删除的是整个后缀while(l<r){int mid=l+r>>1;if(arr[mid]>=target) r=mid;else l=mid+1;}return l;}
}

2、双指针

思路：

• 先找出数组两端的最长非递减前缀和最长非递减后缀 l和r
• res=min(删前缀，删后缀）
• 枚举前缀的每一个点l作为最右端点  用双指针在后缀中找到第一个比arr[l]大的数
• 不断更新最小res=min（r-l-1）

class Solution {public int findLengthOfShortestSubarray(int[] arr) {int n=arr.length;//先找出数组两端的最长非递减前缀和最长非递减后缀int l=0,r=n-1;while(l+1<n&&arr[l]<=arr[l+1]) l++;while(r-1>=0&&arr[r]>=arr[r-1]) r--;if(l>=r) return 0;int res=Math.min(r,n-1-l);for(int i=0;i<=l;i++){while(r<n&&arr[r]<arr[i]) r++;res=Math.min(res,r-i-1);}return res;}
}

这里不甘心非要放个我的最长上升子序列（误

class Solution {public int findLengthOfShortestSubarray(int[] arr) {int n=arr.length;int[] f=new int[n+1]; //f[i]以下标i为结尾的最长上升子序列长度for(int i=0;i<n;i++){f[i]=1;for(int j=0;j<i;j++)if(arr[i]>=arr[j])f[i]=Math.max(f[i],f[j]+1);}int res=-1;for(int i=0;i<n;i++) res=Math.max(res,f[i]);return n-res;}
}