↓Skip to main content
  1. Posts/

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

·1 min·
Table of Contents

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

Solution 1 #

我们可以先排序, 再找出排序后数组和原数组不一样的左右边界. 复杂度 $O(nlogn)$ 代码如下:

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        nums2 = sorted(nums)
        l, r = -1, -1
        n = len(nums)
        for i in range(n):
            if nums[i] != nums2[i]:
                l = i
                break
        for i in range(n - 1, -1, -1):
            if nums[i] != nums2[i]:
                r = i
                break
        return r - l + 1 if r != -1 else 0

Solution 2 #

从左到右遍历, 最后一个小于前面元素最大值的元素是右边界. 左边界同理可得. 这种做法的复杂度是 $O(n)$ . 代码如下:

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        minv, maxv = inf, -inf
        l, r = -1, -1
        for i in range(n):
            if maxv > nums[i]: # 
                r = i
            else:
                maxv = nums[i]
            if minv < nums[n - i - 1]:
                l = n - i - 1
            else:
                minv = nums[n - i - 1]
        return 0 if r == -1 else r - l + 1