给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组,并输出它的长度。
我们可以假设把这个数组分成三段,左段和右段是标准的升序数组,中段数组虽是无序的,但满足最小值大于左段的最大值,最大值小于右段的最小值。
那么我们目标就很明确了,找中段的左右边界,我们分别定义为 L 和 R;
先只考虑中段数组,设其左边界为L,右边界为R:
很明显:
那么有:
public class LeetCode581 {
public int findUnsortedSubarray(int[] nums) {
//右边界从左往右遍历;左边界从右往左遍历
int max = nums[0];
int min = nums[nums.length - 1];
int L = 0,R = -1;
for (int i = 1; i < nums.length; i++) {
//左 ---> 右;寻找[0,R]最大值为max,最后一个小于max的为右边界
if (max <= nums[i]){
max = nums[i];
}else {
R = i;
}
//右 ---> 左;寻找[L,nums.length-1]min,最后一个大于min的为左边界
if (min >= nums[nums.length - i - 1]){
min = nums[nums.length - i -1];
}else {
L = nums.length - i - 1;
}
}
return R - L + 1;
}
}
R右边界需要初始化为-1,要不完美的输入不需要调整,返回+1会出问题