package demo;

import java.util.Arrays;

public class P54 {
//乱序数组，计算需要排序的最小范围，使得数组变为增序
//思路：扫描两轮，分别确定左、右端点。
//从左往右，却出现(相对于历史高点的)下折，要移动右端点；同理，确定左端点。
public static void main(String[] args) {
int[] arr= {2,3,7,5,4,6};
int[] res=sortRange(arr, arr.length);
System.out.println(Arrays.toString(res));
}

static int[] sortRange(int[] arr,int n) {
	int left=-1;		//左、右边界	
	int right=-1;
	int max=arr[0];		//历史最高点、历史最低点
	int min=arr[n-1];
	//从左往右扫描，根据  低于历史最高点  移动右端点
	for(int i=0;i<n;i++) {
		if(arr[i]>max) {
			max=arr[i];
		}
		else if(arr[i]<max) {
			right=i;
		}
	}
	//从右往左扫描，根据  高于历史最低点  移动左端点
	for(int i=n-1;i>=0;i--) {
		if(arr[i]<min) {
			min=arr[i];
		}
		else if(arr[i]>min) {
			left=i;
		}
	}
	return new int[]{left,right};
}

}