难度: Medium
给定一个整数数组，编写一个函数，找出索引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]
提示：
0 <= len(array) <= 1000000
Submission
运行时间: 42 ms
内存: 35.1 MB
class Solution:
def subSort(self, array: List[int]) -> List[int]:
n = len(array)
min_val = float("inf")
max_val = float("-inf")
start, end = -1, -1
for i in range(n):
if array[i] < max_val:
end = i
else:
max_val = array[i]
for i in range(n-1, -1, -1):
if array[i] > min_val:
start = i
else:
min_val = array[i]
return [start, end]
Explain
题解采用了一种扫描数组的方式，首先从左到右扫描，记录最大值，如果当前元素小于已记录的最大值，则更新结束位置end。这样可以找到右侧第一个需要排序的位置。然后从右到左扫描，记录最小值，如果当前元素大于已记录的最小值，则更新开始位置start。这样可以找到左侧第一个需要排序的位置。这两次扫描共同确定了最短需要排序的子数组。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def subSort(self, array: List[int]) -> List[int]:
n = len(array) # 数组长度
min_val = float('inf') # 用于从右向左扫描的最小值初始化
max_val = float('-inf') # 用于从左向右扫描的最大值初始化
start, end = -1, -1 # 初始化结果位置
# 从左向右扫描，找到第一个顺序错误的位置
for i in range(n):
if array[i] < max_val: # 如果当前元素小于已知最大值，更新结束位置
end = i
else: # 否则，更新最大值
max_val = array[i]
# 从右向左扫描，找到第一个顺序错误的位置
for i in range(n-1, -1, -1):
if array[i] > min_val: # 如果当前元素大于已知最小值，更新开始位置
start = i
else: # 否则，更新最小值
min_val = array[i]
return [start, end] # 返回需要排序的子数组的起始和结束位置
Explore
此算法的目的是找到最小的子数组，当对其进行排序后，整个数组都将是有序的。从左到右扫描时，通过更新最大值并检查当前元素是否小于此最大值，可以确定右边界。如果元素小于最大值，意味着它应该位于更前面的位置。相反，从右到左扫描通过更新最小值，如果当前元素大于此最小值，则意味着它应该位于更后面的位置，从而确定左边界。这两次扫描确保找到的子数组是最短的，使其排序后整个数组变为有序。
在代码中，初始设置了`start`和`end`索引为`-1`。在从左到右的扫描中，如果所有元素都是递增的，则`max_val`将逐步更新而不会触发`end`的更新（即不会有任何元素小于`max_val`）。类似地，在从右到左的扫描中，如果所有元素都是递减的，则`min_val`也将逐步更新而不会触发`start`的更新（即不会有任何元素大于`min_val`）。因此，如果数组已经完全排序，`start`和`end`将保持为初始值`-1`，最终返回`[-1, -1]`。
此条件用于检查当前元素是否处于正确的位置。在从左到右扫描过程中，`max_val`记录了扫描到当前位置时的最大值。如果某个元素`array[i]`小于`max_val`，这说明`array[i]`位于比它大的元素之后，这是无序的，因此需要对其进行排序。由此，`end`索引会被更新为当前元素的位置，标记这是目前找到的最右侧的无序位置。这个逻辑确保了能够找到需要排序的最小子数组的右边界。