ac

给定一个无序数组arr，求出需要排序的最短子数组的长度，对子数组排序后能使得整个数组有序，即为需要排序的数组。例如：arr=[1,5,3,4,2,6,7]返回4，因为只有[5,3,4,2]需要排序。

时间复杂度O(n),额外空间复杂度O(1)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            int val = sc.nextInt();
            arr[i] = val;
        }
        int ans = getMinLen(arr);
        // print 结果
        System.out.println(ans);
    }

    static int getMinLen(int[] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
        int noMinIndex = -1; // 记录按照排序，左侧最后不符合的位置
        int minVal = arr[arr.length - 1]; // 从右往左遍历，遍历的过程中记录右侧出现过的数的最小值
        for(int i=arr.length-2;i>=0;i--){
            if(arr[i] > minVal){ // 那么arr[i]必须移动到 minVal的左边
                noMinIndex = i;
            }else {
                minVal = Math.min(minVal, arr[i]);
            }
        }
        if(noMinIndex == -1){ // 说明从右到左一直是降序的
            return 0;
        }
        int noMaxIndex = -1; // 记录按照排序，右侧最后不符合的位置
        int maxVal = arr[0];// 从左往右遍历，遍历的过程中记录左侧出现过的数的最大值
        for(int i=1;i<arr.length;i++){
            if(arr[i] < maxVal){ // arr[i] 必须移动到minVal的右边
                noMaxIndex = i;
            }else {
                maxVal = Math.max(minVal, arr[i]);
            }
        }
        return noMaxIndex - noMinIndex + 1;
    }

}
/*
7
1 5 3 4 2 6 7

4
*/