需要排序的子数组

题目描述

给定一个无序数组arr，求出需要排序的最短子数组长度
要求：O(N)
如输入：arr={2,3,7,5,4,6}，返回4，因为只有{7,5,4,6}需要排序。

分析

以{2,3,7,5,4,6,8,9}为例：

前端小于最小波谷（3）的部分线段不用排序，所以{2,3}不用排序
后端大于最大波峰（7）的部分线段不用排序，所以{8,9}不用排序
注意，起点可能是波峰，终点可能是波谷。

package com.company;

import com.company.util.ArrayUtil;
import org.omg.CORBA.INTERNAL;

import java.util.Arrays;

public class Test9 {
    public static void main(String[] args) {
//        int[] arr={2,3,3,7,5,4,6,8,9};
//        int[] arr={2,3,4,5,6,7};
//        int[] arr={7,5,4,6,2,3};
//        int[] arr={3, 9, 3, 2, 0, 0};
        int[] arr=ArrayUtil.randomArray(0,10,6);
//        求最大波峰，最小波谷
        int max=Integer.MIN_VALUE,min=Integer.MAX_VALUE;
        if(arr[0]>arr[1]){
            max=arr[0]>max?arr[0]:max;

        }
        for (int i = 1; i < arr.length-1; i++) {

            if(arr[i]>=arr[i-1]&&arr[i]>=arr[i+1]){//波峰
                max=arr[i]>max?arr[i]:max;
            }

            if(arr[i]<=arr[i-1]&&arr[i]<=arr[i+1]){//波谷

                System.out.println(arr[i]);
                min=arr[i]<min?arr[i]:min;
            }

        }
        if( arr[arr.length-2]>arr[arr.length-1]){
            min=arr[arr.length-1]<min?arr[arr.length-1]:min;

        }
        System.out.println("max="+max);
        System.out.println("min="+min);
        //前面小于min的元素个数
        int c1=0,c2=0;
        if(arr[0]<=min) {
            c1++;
            int i = 1;
            while (arr[i] <=min && arr[i] >= arr[i - 1]) {
                i++;
                c1++;
            }
        }

        System.out.println("c1="+c1);
//        后面大于max的元素个数
        if(arr[arr.length-1]>=max) {
            c2++;
            int i = arr.length - 2;
            while (arr[i] >= max && arr[i] <= arr[i + 1]) {
                i--;
                c2++;
            }
        }

        System.out.println("c2="+c2);
        int sortLen=c1>c2?c1:c2;
        System.out.println(sortLen);
        System.out.println(Arrays.toString(arr));
        System.out.println(arr.length-sortLen);

    }
}