最短无序连续子数组

题目描述

给定一个整数数组 nums，请你找出一个连续的子数组，使得只要把这个子数组按升序排序，整个数组都会变为升序排序。

返回满足条件的最短子数组的长度。如果整个数组已经有序，返回 0。

输入格式

第一行一个正整数 n，表示数组长度。

第二行 n 个整数，表示数组 nums。

输出格式

一行一个整数，表示最短子数组的长度。

样例

7
2 6 4 8 10 9 15

5

4
1 2 3 4

0

5
5 4 3 2 1

5

样例解释

• 样例 1：子数组 [6,4,8,10,9]（第 2 到第 6 个元素）排序后数组变为 [2,4,6,8,9,10,15]，整个数组有序。不存在更短的满足条件的子数组，答案为 5。
• 样例 2：数组已经有序，无需排序任何子数组，答案为 0。
• 样例 3：整个数组逆序，必须排序全部 5 个元素才能使数组有序，答案为 5。

数据范围

• 1 ≤ n ≤ 10^4
• -10^5 ≤ nums[i] ≤ 10^5

提示

将数组与排序后的版本比较，从左找到第一个不匹配的位置，从右找到最后一个不匹配的位置，二者之间的距离即为答案。时间复杂度 O(n log n)，空间复杂度 O(n)。