部分排序

一、题目描述

题目链接：https://leetcode-cn.com/problems/sub-sort-lcci/

 

二、题目分析

题解参考：https://leetcode-cn.com/problems/sub-sort-lcci/solution/yi-bian-bian-li-shuang-zhi-zhen-by-chen-wei-zhe/

我们从左到右遍历，如果说数组是升序的，就不用操作，如果遇到一个数字跟前面的数组无法组成升序序列，那这个数字就是需要交换的，我们记录这个下标位lastIndex，然后继续遍历下去，如果后面还有不符合这个条件的，就更新lastIndex，因为大的lastIndex会把前面的覆盖。这样子我们就找到了lastIndex。

然后我们再从右往左遍历，这样子数组应该得是降序才能符合要求，做法跟前面是类似的，我们维护一个firstIndex，如果又不符合降序就更新，最后也会找到一个firstIndex。

 

三、代码

    public int[] subSort(int[] array) {
        int len = array.length;
        if (len == 0) return new int[]{-1,-1};
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int first = -1;
        int last = -1;
        for (int i = 0; i < len; ++i) {
            if (array[i] < max) {
                last = i;
            } else {
                max = array[i];
            }
            if (array[len - 1 - i] > min) {
                first = len - 1 - i;
            } else {
                min = array[len - 1 - i];
            }
        }
        return new int[]{first, last};
    }