题目描述 #

581.最短无序连续子数组
给你一个整数数组nums，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的最短子数组，并输出它的长度。

示例 1： #

输入：nums = [2,6,4,8,10,9,15]  
输出：5  
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2： #

输入：nums = [1,2,3,4]  
输出：0  

思路 #

两头判断，左边应一直为递增，右边应一直为递减

1. 定义双指针，low和high，分别对应nums.length-1、0
2. 定义俩个值，min和 max，分别对应nums[nums.length-1]、nums[0]
3. 循环数组，i为当前循环的下标，从1开始,len=nums.length
4. 取Math.min(nums[len-i-1], min)
   • 因为min定义为数组最后一项，如果它的前一项比他大，即nums[len-i-1]>min，说明倒数两项不是递减，需要更改low=len-i-1
5. 取Math.max(nums[i], max)
   • 因为max定义为数组第一项，如果它比它的后一项大，即max>nums[i]，说明前两项不是递增，需要更改high=i
6. 如果数组一直是递增的，那最后high和low的值不会发生变化，即high<low,直接返回0
7. 如果存在不是递增的子序列，则high>low，返回high-low+1

题解 #

var findUnsortedSubarray = function(nums) {
    let len = nums.length
    let [min, max] = [nums[len-1],nums[0]]
    let [low, high] = [len-1, 0]
    for(let i=1;i<len;i++){
        min = Math.min(min, nums[len-i-1])
        max = Math.max(max, nums[i])
        if(nums[len-i-1]>min){
            low = len-i-1
        }
        if(max>nums[i]){
            high = i
        }
    }
    return high>low?high-low+1:0
};