Leecode 面试题 #16.16 部分排序

给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

示例

输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]

解题思路

确定左右两侧已经达到有序的部分，标记中left和right，而中间部分mid是无序的，我们只需要向左右扩展这个mid，使其满足min(mid)>left[-1] and max(mid) < right[0].

class Solution:
    def subSort(self, array):
        if len(array) <2:
            return [-1 ,-1]
        l = len(array)
        for i in range(l-1):
            if array[i] > array[i+1]:
                break
        left = i + 1
        if left == l-1:
            return [-1, -1]
        
        for i in range(l-1, -1, -1):
            if array[i] < array[i-1]:
                break
        right = i

        mid = array[left:right]
        mmin = min(mid)
        mmax = max(mid)
        
        while True:
            if left > 0 and array[left-1] > mmin:
                left -= 1
                mmax = max(mmax, array[left])

            elif right < l-1 and array[right+1] < mmax:
                right += 1    
                mmin = min(mmin, array[right])
            else:
                return [left, right]
                

时间和空间上都达到了100%，思路简单但是代码不好写，尤其是求左右边界的时候容易出错，后面的边界扩张部分也会有小细节