581. 最短无序连续子数组

给你一个整数数组 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;


    }
}

  

上一篇:【DB笔试面试581】在Oracle中,绑定变量是什么?绑定变量有什么优缺点?


下一篇:Codeup刷题笔记581:《算法笔记》练习题4.1节