高速公路建设管理局网站,课程网站建设ppt模板下载,怎么做网站最便宜,建网站不花钱免费建站题目#xff1a;
给你一个整数数组 arr #xff0c;请你删除一个子数组#xff08;可以为空#xff09;#xff0c;使得 arr 中剩下的元素是 非递减 的。
一个子数组指的是原数组中连续的一个子序列。
请你返回满足题目要求的最短子数组的长度。
示例 1#xff1a;
…题目
给你一个整数数组 arr 请你删除一个子数组可以为空使得 arr 中剩下的元素是 非递减 的。
一个子数组指的是原数组中连续的一个子序列。
请你返回满足题目要求的最短子数组的长度。
示例 1
输入arr [1,2,3,10,4,2,3,5] 输出3 解释我们需要删除的最短子数组是 [10,4,2] 长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。 另一个正确的解为删除子数组 [3,10,4] 。 示例 2
输入arr [5,4,3,2,1] 输出4 解释由于数组是严格递减的我们只能保留一个元素。所以我们需要删除长度为 4 的子数组要么删除 [5,4,3,2]要么删除 [4,3,2,1]。 示例 3
输入arr [1,2,3] 输出0 解释数组已经是非递减的了我们不需要删除任何元素。 示例 4
输入arr [1] 输出0
提示
1 arr.length 10^5 0 arr[i] 10^9
java代码
class Solution { // 模板二public int findLengthOfShortestSubarray(int[] arr) {int n arr.length;int i 1, j n-1;while (in arr[i-1]arr[i]) i;if (i n) return 0; // arr已经有序while (j-10 arr[j-1]arr[j]) --j;int l j, r n-1; int ans j; // 最坏结果只保留rightfor (int k 0; k i; k) {int target arr[k];l j; r n; //搜索right区间[j,n-1]while (lr) {int mid (lr)1;if (arr[mid] target) {l mid1;} else {r mid;}}ans Math.min(ans, r-k-1);}return ans;}
}
