算法挑战100天 - six(mid)

类别：数组

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

我的解：错误解没搞定

public int[] subSort(int[] nums) {
        int tempTop = 0;
        int tempLow = 0;
        if(nums.length < 2){
            return new int[]{-1, -1};
        }
        for (int i = 0; i < nums.length; i++) {
            if (i+1<nums.length && nums[i] > nums[i + 1]) {
                if (tempTop > i) {
                    tempTop = i;
                }
            }
        }

        for (int i = nums.length-1; i >= 0; i--) {
            if (i+1<nums.length && nums[i] < nums[i+1]) {
                if (tempLow > i) {
                    tempLow = i-1;
                }
            }
        }
        if(tempTop == tempLow){
            return new int[]{-1, -1};
        }
        return new int[]{tempTop, tempLow};
    }

最优解：时间 O(n) 空间O(1)

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

            if(array[len - 1 - i] > min){
                first = len - 1 - i;
            }else{
                min = Math.min(min, array[len - 1 - i]);
            }
        }
        return new int[] {first, last};
    }

差异点：

1.没有利用数据特性，没想到当右侧索引位置数据一定比左侧数据中最大的小，就是需要排序，相反左侧索引位置数据一定比右侧数据中最小的数据大，就要排序；