题目描述

给定一个无序数组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);}
}