584.最短无序连续子数组

题目描述

题解

方法一(时间复杂度不好)

所求的子数组一定是以两个降序元素开始, 并以两个降序元素结尾的.

比如题目的实例中, 以6和4作为所求数组的开始, 以10和9作为所求数组的结尾.

public int findUnsortedSubarray(int[] nums) {
    int l = nums.length;
    int r = 0;
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] > nums[j]) {
                l = Math.min(i, l);
                r = Math.max(j, r);
            }
        }
    }

    if (l == nums.length) {
        return 0;
    }
    return r - l + 1;
}

方法二:排序

先将数组排序, 然后逐一比对, 记下首个不同的元素和最后一个不同的元素

代码略

方法三:推荐

根据无序连续子数组的性质, 找出子数组中的最大值和最小值, 第一个大于该最小值的位置为子数组的左界, 从右边开始第一个小于最大值的位置为子数组的右界

public class lc581 {
    public int findUnsortedSubarray(int[] nums) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                min = Math.min(min, nums[i+1]);
                max = Math.max(max, nums[i]);
            }
        }

        int l = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > min) {
                l = i;
                break;
            }
        }

        int r = 0;
        for (int i = nums.length-1; i >= 0; i--) {
            if (nums[i] < max) {
                r = i;
                break;
            }
        }


        return l == r ? 0 : r - l + 1;

    }

}