#yyds干货盘点# LeetCode程序员面试金典：部分排序

题目：

给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

示例：

输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]

输出： [3,9]

代码实现：

class Solution {
    public int[] subSort(int[] array) {
        if (array.length <= 1) {
            return new int[]{-1, -1};
        }
        return err(array,0,array.length-1);
    }

    public static int[] err(int[] a, int left, int right) {
        int l = -1;
        int r = -1;
        int max = a[left];
        int min = a[right];
        for (int i = left; i <= right; i++) {
            if (a[i] >= max) {
                max = a[i];
            }else {
                r = i;
            }
        }
        if(r == -1){
            return new int[]{-1, -1};
        }
        for (int i = right; i>=left; i--){
            if (a[i] <= min) {
                min = a[i];
            }else {
                l = i;
            }
        }
        return new int[]{l, r};
    }
}