[Python手撕]部分排序

class Solution:
    def subSort(self, array: List[int]) -> List[int]:

        n = len(array)
        start, end = -1, -1

        # 从前往后找到第一个逆序
        for i in range(n - 1):
            if array[i] > array[i + 1]:
                start = i + 1
                break

        if start == -1:
            return [-1, -1]

        # 从后往前找到第一个逆序
        for j in range(n - 1, 0, -1):
            if array[j - 1] > array[j]:
                end = j - 1
                break

        # 逆序中的最小值和最大值
        min_value = min(array[start : end + 1])
        max_value = max(array[start : end + 1])

        left, right = 0, n - 1
        # 从逆序数组向两侧扩展，找到比逆序数组更极端的左右两个数字
        for i in range(start - 1, 0, -1):
            if array[i] <= min_value:
                left = i + 1
                break
        for j in range(end + 1, n):
            if array[j] >= max_value:
                right = j - 1
                break

        return [left, right]