部分排序

题目

题目来源：力扣（LeetCode）

给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
示例：

输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]

思路分析

默认升序（降序也只是改一点代码，不影响）
原理：如果左侧最大值大于中间的最小值，则一定会被中间序列包括；同理，如果右侧最小值大于中间的最大值，则一定会被中间序列包括。

一遍遍历 + 两个指针（两次扫描可一次遍历完成）
1、从前向后扫描数组，判断当前array[i]是否比max小，是则将last置为当前array下标i，否则更新max;
2、从后向前扫描数组，判断当前array[len - 1 - i]是否比min大，是则将first置位当前下标len - 1 - i，否则更新min;
3、返回{first， last}

/**
 * @param {number[]} array
 * @return {number[]}
 */
var subSort = function (array) {
    // 头指针，尾指针
    let r = -1, l = -1;
    // 从左向右遍历，如果当前元素比它之前的最大的元素小，说明不是升序的，更新 r 为当前元素索引，继续遍历直到末尾
    let max = Number.MIN_SAFE_INTEGER;
    for (let i = 0; i < array.length; i++) {
        if (array[i] >= max) {
            max = array[i];
        } else {
            r = i;
        }
    }
    // 从右向左遍历，如果当前元素比它之后的最小的元素大，说明不是降序的，更新 l 为当前元素索引，继续遍历直到开始
    let min = Number.MAX_SAFE_INTEGER;
    for (let i = array.length - 1; i >= 0; i--) {
        if (array[i] <= min) {
            min = array[i]
        } else {
            l = i;
        }
    }
    return [l, r];
};