Interview Question - minimum length to sort array

这是网上看到的一道面经题目，觉得很有意思。总结下。

题目：
给你一个未排序的数组，问最短从这个数组的那一段开始排序即能让整个数组有序
比如(1,2,5,7,6,4,9)，那么从 (5,7,6,4)这一段排序就足够了
最坏情况O(N^2)，最优情况O(N)时间O(1)空间

My code:

public int getMinLength(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            continue;
        }
        else {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i - 1]);
        }
    }
    
    if (max == Integer.MIN_VALUE) {
        return 0;
    }
    
    int begin = 0;
    int end = nums.length - 1;
    while (nums[begin] < min) {
        begin++;
    }
    
    while (nums[end] > max) {
        end--;
    }
    
    System.out.println("We should sort: [" + begin + ", " + end + "]");
    return end - begin + 1;
}

自己参考了答案才写出来。

reference:
http://stackoverflow.com/questions/15855594/min-n-m-so-that-whole-array-will-be-sorted/15855670#15855670

Anyway, Good luck, Richardo! -- 09/13/2016