力扣581题题解

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]

输出：5

解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]

输出：0

示例 3：

输入：nums = [1]

输出：0

提示：

1 <= nums.length <= 104

-105 <= nums[i] <= 105

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

思路：

本题如果用先排序后对比最前位置和最后位置值不同的差异也能够pass,但是这种就无法在O(n)时刻获取到结果。

今天分享一个能够用O(n)时间复杂度获取结果的方法。

1、从左往右遍历数组找到递增断掉的位置i，赋值给min

2、从右向左遍历数组找到递减断掉的位置j，赋值给max

3、从i到j我们遍历每一个位置找以下两种情况

        3.1、当前位置t的数据比min还小，则从i到0开始遍历扩大需要调整顺序的数组范围。因为这个时候需要调整的顺序数组需要韩该t位置数据。只能往前移动寻找。

        3.2、当前位置t的数据比max还大，则从j到len开始遍历扩大需要调整顺序的数组范围。因为这个时候需要调整顺序的最大范围有变动，不是我们在第2步找到的位置，那么只能往右找能够覆盖t位置数据的位置。

        这样下来我们在O(n)时间范围内就可以找到需要排序的范围。

 public int findUnsortedSubarray(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int i = 0;
        int j = nums.length - 1;
        while ((i+1) < nums.length && nums[i+1] >= nums[i ]) {
            i++;
        }
        if(i==nums.length){
            return 0;
        }
        int min = nums[i];
        while ((j-1)>=0 && nums[j - 1] <= nums[j]) {
            j--;
        }
        if(j<i){
            return 0;
        }
        int left=MIN;
        int right=MAX;
        int max = nums[j];
        for (int t = i; t <= j; t++) {
            if(nums[t]<min){
                for(int l=i;l>=0;l--){
                    if(nums[t]<nums[l]){
                        min=nums[l];
                        left=l;
                    }
                }

            }
            if(nums[t]>max){
                for(int l=j;l<nums.length;l++){
                    if(nums[t]>nums[l]){
                       max=nums[l];
                       right=l;
                    }
                }
            }
        }
        return  right==left?0:right-left+1;


    }