0581：最短无序连续子数组（★）

2015-01-01 约 378 字预计阅读 1 分钟次阅读

力扣第 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 <= 10⁴
-10⁵ <= nums[i] <= 10⁵

进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？

分析

#1

排序后找第一个和最后一个不相等的位置即可。

1
2
3
4
5
6
7
8


class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        i,j = n+1,n
        for k,(x,y) in enumerate(zip(nums,sorted(nums))):
            if x!=y:
                i,j = min(i,k),k
        return j-i+1

66 ms

#2

要求 O(N)，可以换种方式判断
左边界即是第一个不满足 nums[i]<=min(nums[i:]) 的位置 i
右边界即是最后一个不满足 nums[j]>=max(nums[:j]) 的位置 j

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        i,j = n+1,n
        mi = inf
        for k in range(n-1,-1,-1):
            if nums[k]>mi:
                i = k
            mi = min(mi,nums[k])
        ma = -inf
        for k in range(n):
            if nums[k]<ma:
                j = k
            ma = max(ma,nums[k])
        return j-i+1

74 ms

目录

0581：最短无序连续子数组（★）

题目

分析

#1

#2

解答