【LeetCode-581】最短无序连续子数组

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

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

示例 1:

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

输入:nums = [1,2,3,4]
输出:0
示例 3:

输入:nums = [1]
输出:0
 

提示:

1 <= nums.length <= 104
-105 <= nums[i] <= 105

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题报告:

时间复杂度O(nlogn)的就不说了。来看看O(n)的。

首先不难证明,如果要找的区间的左右端点也必须参与排序(即不能排序后位置不变),则这个区间是唯一的。所以就不存在最短区间这一说了,直接就找,必须参与排序的这个区间就好了。

对于我们要找到的最短区间的左端点:

从左到右扫描每一个i,如果nums[i]是后缀最小值,则他一定不是左端点,因为他不需要参与排序。因此我们只需要找到左起第一个不是后缀最小值的nums[i],那么i就是左端点。

右端点同理。

因此具体到实现方式,可以从右向左维护一个后缀最小值数组,从左到右维护一个前缀最大之数组,然后随便搞一下维护结果就好了。

AC代码:

func min(a,b int) int{
    if a<b {
        return a
    } 
    return b
}
func max(a,b int)int{
    if a>b {
        return a
    } 
    return b
}
func findUnsortedSubarray(nums []int) int {
    n := len(nums)
    Rmin := make([]int, n)
    Lmax := make([]int, n)
    ansl, ansr := 0,-1 //为了保证初始len为0
    
    Rmin[n-1] = nums[n-1]
    for i:=n-2; i>=0; i-- {
        Rmin[i] = min(nums[i], Rmin[i+1])
    }
    Lmax[0] = nums[0]
    for i:=1;i<n;i++ {
        Lmax[i] = max(nums[i], Lmax[i-1])
    }

    for i,v := range(Rmin) {
        if v != nums[i] {
            ansl = i;
            break;
        }
    }
    for i:=n-1;i>=0;i-- {
        if Lmax[i] != nums[i] {
            ansr = i;break;
        }
    }
    return ansr - ansl + 1;

}

// [1,2,5,7,6]

上一篇:LeetCode 581. 最短无序连续子数组


下一篇:【DB笔试面试581】在Oracle中,绑定变量是什么?绑定变量有什么优缺点?