面试题 16.16. 部分排序

class Solution {
    public int[] subSort(int[] array) {
        int[] res = new int[2];
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        int firstIndex = -1, lastIndex = -1;
        for (int i = 0; i < array.length; i++) {
            if (array[i] < max) {
                lastIndex = i;
            } else {
                max = Math.max(max, array[i]);
            }

            if (array[array.length - i - 1] > min) {
                firstIndex = array.length - 1 - i; // 注意此处记录的索引为 array.length - 1 - i
            } else {
                min = Math.min(min, array[array.length - i - 1]);
            }
        }

        res[0] = firstIndex;
        res[1] = lastIndex;
        return res;
    }
}

References

面试题 16.16. 部分排序