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

• 题目描述：对于一个无序数组A，请设计一个算法，求出需要排序的最短子数组的长度。 给定一个整数数组A及它的大小n，请返回最短子数组的长度。
• 要求：时间复杂度O(n) 空间复杂度O(1)

• 例子： [1,5,3,4,2,6,7],7

  返回：4

算法描述：

1. 从左往右找”当前值比max小”的一系列情况：

初始：max=arr[0]；

如果当前元素比max大，max就等于当前元素；

如果当前元素比max小，max不变，然后继续往后找,直到最后一次出现”当前值比max小”的情形，记下此时的下标为k。

2. 从右往左找”当前值比min大”的一系列情况：

初始：min=arr[6];

如果当前元素比min小，min就等于当前元素；

如果当前元素比min大，min不变，然后继续往前找，直到最后一次出现就”当前值比min大”的情形，记下此时的下标为j。

3. 长度=k-j+1。

过程演示：

1. 从左往右找的过程：

max= arr[0]=1

max < arr[1] ,max=arr[1]=5

max > arr[2], 此时开始出现max > 当前值的情况

max > arr[3]

max > arr[4]

max < arr[5],max=arr[5]

max < arr[6]

故arr[4]最后一次出现这种情况的位置，记录下来，此时为k = 4

注意：如果数组是[1,5,3,4,2,6,7,0],则
…
max=arr[5],max=arr[5]
max<arr[6],max=arr[6]
max>arr[7]=0,故最后一次出现”max>当前值”的情况是k=7   
           

2 . 从右往左的过程

(在c语言中给数组长度，可以直接定位到数组最右端)

min = arr[6] = 7

min > arr[5], min=arr[5]=6

min > arr[4], min=arr[4]=2

min < arr[3]=4

min < arr[2]=3

min < arr[1]=5

min > arr[0]=1，故arr[1]是最后一次出现这种情况的位置，记录下来，此时为j=1

综上，从j=1到k=4这个下标出是需要排序的部分，长度为4。

代码实现：

/**最短排序
 * 对于一个无序数组A，请设计一个算法，求出需要排序的最短子数组的长度。
 * 给定一个整数数组A及它的大小n，请返回最短子数组的长度。
 * 时间复杂度O(n) 空间复杂度O(1)
 * [1,5,3,4,2,6,7],7
 * 返回：4
 * @author FanFF
 * 
 */
public class ShortSubsequence {
    public static void main(String[] args) {
        int []arr = {,,,,,,};
        System.out.println(getMinLength(arr));
    }

    public static int getMinLength(int[] arr) {
        if (arr == null || arr.length < ) {
            return ;
        }
        int min = arr[arr.length - ];
        int MinIndex = -;
        for (int i = arr.length - ; i != -; --i) {// 从右往左
            if (arr[i] > min) {// 当前值 > min
                MinIndex = i;
            } else {
                min = arr[i];
            }
        }
        if (MinIndex == -) {
            return ;
        }
        int max = arr[];
        int MaxIndex = -;
        for (int i = ; i != arr.length; i++) {// 从左往右
            if (arr[i] < max) {// 当前值 < max
                MaxIndex = i;
            } else {
                max = arr[i];
            }
        }
        return MaxIndex - MinIndex + ;
    }
}