需要排序的最短子數組的長度

• 題目描述：對于一個無序數組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 + ;
    }
}