Leetcode 581. 最短无序连续子数组

题目描述

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

你找到的子数组应是最短的，请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]

输出: 5

解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

解法

以 left、right、maxIndex 分别作为待求子数组的左边界、右边界和最大值。由左向右遍历数组，并更新最大值下标。若当前元素小于最大值，则更新右边界 right 值，并由 left 向左遍历，直到元素不大于右边界 right 指向值。最终子数组长度为 right - left + 1。

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        left,right,maxIndex=None,0,0
        for i in range(1,len(nums)):
            if nums[i]>=nums[maxIndex]:
                maxIndex=i
            else:
                right=i
                if left==None:
                    left=i-1
                while left>0 and nums[left-1]>nums[right]:
                    left-=1
        return right-left+1 if left!=None else 0