题解|需要排序的子数组长度（锯齿形数组）

需要排序的子数组

题目描述
给定一个无序数组arr，求出需要升序排序的最短子数组长度
如输入：arr = {2，3，7，5，4，6}，返回4，因为只有{7，5，4，6}需要排序

思路

1. 确定数组最大值位置，从该位置向右扫描寻找是否有小于最大值的元素，若有则扩大需要排序区间的右端。
2. 确定数组最小值位置，从该位置向左扫描寻找是否有大于最小值的元素，若有则扩大需要排序区间的左端。
3. 得出左右端点即可计算长度
   
   源代码

public class 需要排序的最短子数组长度 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 2, 3, 7, 5, 4, 1, 6, 7 };
		int indexOfMin = 0;
		int indexOfMax = 0;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] < indexOfMin) {
				indexOfMin = i;
			}
			if (arr[i] > indexOfMax) {
				indexOfMax = i;
			}
		}
		int left = getLeft(arr, indexOfMin);
		int right = getRight(arr, indexOfMax);
		int len = right - left + 1;
		System.out.println(len);
	}

	private static int getLeft(int[] arr, int indexOfMin) {
		int left = indexOfMin;
		for (int i = indexOfMin - 1; i >= 0; i--) {
			if (arr[i] > indexOfMin) {
				left = i;
			}
		}
		return left;
	}

	private static int getRight(int[] arr, int indexOfMax) {
		int right = indexOfMax;
		for (int i = indexOfMax + 1; i < arr.length; i++) {
			if (arr[i] < arr[indexOfMax]) {
				right = i;
			}
		}
		return right;
	}
}