难度: Medium
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
示例 1：
输入：nums = [2,6,4,8,10,9,15] 输出：5 解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：
输入：nums = [1,2,3,4] 输出：0
示例 3：
输入：nums = [1] 输出：0
提示：
1 <= nums.length <= 104-105 <= nums[i] <= 105
进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
运行时间: 24 ms
内存: 17.4 MB
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
n = len(nums)
# 原理：最小元素左边比它大的元素都要参与排序，最大元素右边比它小的元素都要调整
# 首先找满足单调的两边。
l,r = -1, -1
for i in range(1, n):
if nums[i-1] > nums[i]:
l = i-1
break
for i in range(n-1, 0, -1):
if nums[i-1] > nums[i]:
r = i
break
if l < 0:
return 0
Min, Max = min(nums[l:r+1]), max(nums[l:r+1])
while l > 0 and Min < nums[l-1]: # 满足除此之外的最大值（左边）比其中的最小值大
l -= 1
while r < n-1 and Max > nums[r+1]:
r += 1
return r - l + 1
该题解的思路是先找到最短无序连续子数组的候选区间 [l, r]，然后再扩展该区间直到满足条件。具体步骤如下： 1. 从左到右扫描数组，找到第一个破坏升序的位置 l； 2. 从右到左扫描数组，找到最后一个破坏升序的位置 r； 3. 如果没找到 l 和 r，说明数组本身有序，直接返回 0； 4. 在 [l, r] 区间内找到最小值 Min 和最大值 Max； 5. 从 l 开始向左扩展，直到找到第一个小于 Min 的位置，更新 l； 6. 从 r 开始向右扩展，直到找到第一个大于 Max 的位置，更新 r； 7. 返回 r - l + 1 作为最短无序连续子数组的长度。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
n = len(nums)
# 从左到右扫描，找第一个破坏升序的位置
l,r = -1, -1
for i in range(1, n):
if nums[i-1] > nums[i]:
l = i-1
break
# 从右到左扫描，找最后一个破坏升序的位置
for i in range(n-1, 0, -1):
if nums[i-1] > nums[i]:
r = i
break
# 数组本身有序，直接返回 0
if l < 0:
return 0
# 在 [l, r] 区间内找最小值和最大值
Min, Max = min(nums[l:r+1]), max(nums[l:r+1])
# 从 l 向左扩展，直到找到小于 Min 的位置
while l > 0 and Min < nums[l-1]:
l -= 1
# 从 r 向右扩展，直到找到大于 Max 的位置
while r < n-1 and Max > nums[r+1]:
r += 1
# 返回最短无序连续子数组的长度
return r - l + 1
从左到右扫描数组来寻找第一个破坏升序的位置是为了确定无序子数组的起始边界。这种方法确实考虑到了所有可能破坏升序的情况，因为一旦发现一个元素比其前一个元素小，就表明从这一点开始数组已经不再满足全局升序的性质。这个位置标记了可能的无序子数组的开始，这是因为任何在这个位置之前的元素都不需要参与到后续的排序中，以保持整体数组的升序。
从右到左扫描数组以寻找最后一个破坏升序的位置是为了确定无序子数组的结束边界。这一步骤的目的是确保找到从右侧开始的、能够影响数组排序的最后一个元素。如果从左向右扫描，则可能错过右侧边界的准确位置，因为在某些情况下，数组的右侧部分可能比左侧更早破坏升序。从右向左扫描确保可以准确找到任何需要重新排序的元素，从而使整个数组达到全局升序。
区间 [l, r] 的扩展是基于在这个区间内找到的最小值 Min 和最大值 Max。扩展的目的是确保数组中的任何元素如果小于区间的最小值或大于区间的最大值，都必须包括在内以进行重新排序。这是因为，即使 [l, r] 内的元素本身是无序的，如果区间外的元素小于 Min 或大于 Max，那么这些元素也会影响整体数组的排序。因此，为了确保整个数组升序，我们需要将这些元素包括在需要重新排序的子数组中。
是的，这种方法可以准确地确定最短无序连续子数组的起始和结束位置，即使数组中存在多个局部最小或最大值。该方法通过从左到右和从右到左的扫描确定了初始的 [l, r] 区间，然后通过扩展这个区间以包括所有小于 Min 或大于 Max 的元素，确保了捕获所有需要重新排序的元素。这种方式确保了无论局部极值如何分布，最终确定的 [l, r] 区间都将包括所有必须重新排序的元素，从而使整个数组达到全局升序。