给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组,并输出它的长度。
示例 1:
输入:nums = [2,6,4,8,10,9,15]
输出:5
解释:你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。
需要排序的最短子数组长度
1 2 5 4 2 7 6 8 9
0 1 2 3 4 5 6 7 8
使得整体都有序,最少要排的最短子数组,看数据状态
看一下左边和右边不用排的都有多大,那么中间就是要排的
遍历的时候记录一下x>=maxRight达标,记录一下最后一次不达标的位置
最后一次达标说明了再往右都是排好序的,如此下来找到一个右侧确定的区域
接下来,再从右往左遍历, x<=minLeft叫达标,否则不达标,记录一下最后一个不达标的位置
如此下来找到一个左侧确定的区域
3 4 5 6 7 1 2 3
1 2 4 5 6 7 3
1 5 3 4 2 6 7
0 1 2 3 4 5 6
class Solution { public int findUnsortedSubarray(int[] nums) { if(nums.length<=1){ return 0; } int rightMax=nums[0]; int rightIndex=-1; for(int i=1;i<nums.length;i++){ if(nums[i]<rightMax){ rightIndex=i; }else{ rightMax=Math.max(rightMax,nums[i]); } } if(rightIndex==-1){ return 0; } int leftMin=nums[nums.length-1]; int leftIndex=-1; for(int i=nums.length-2;i>=0;i--){ if(nums[i]>leftMin){ leftIndex=i; }else{ leftMin=Math.min(leftMin,nums[i]); } } if(leftIndex==-1){ return 0; } return rightIndex-leftIndex+1; } }