581. 最短无序连续子数组
题目描述
输入一个整数数组 nums。
选出一段连续的子数组，只对这一段按升序排序，其余位置不动，就能让整个数组变成升序。求满足这一条件的最短子数组的长度并返回。
如果数组本来就是升序的，返回 0。
示例 1
输入：nums = [2,6,4,8,10,9,15] 输出：5
解释：只需排序 [6,4,8,10,9] 这 5 个元素。
示例 2
输入：nums = [1,2,3,4] 输出：0
解释：数组已经有序。
示例 3
输入：nums = [1] 输出：0
解释：只有一个元素，自然有序。
数据范围
1 <= nums.length <= 10^4-10^5 <= nums[i] <= 10^5
进阶：能否在 O(n) 时间内解决？
解题思路：两遍扫描找边界
一个位置 i 不用动，当且仅当它不小于左边所有数、且不大于右边所有数。从左往右扫，维护前缀最大值 mx：若 nums[i] < mx，说明 i 必须参与排序，最后一个这样的 i 就是右边界 right。再从右往左扫，维护后缀最小值 mn：若 nums[i] > mn，最后一个（最左的）这样的 i 就是左边界 left。答案是 right − left + 1。它和“单调栈找第一个被弹出的位置”的思路等价，但只用 O(1) 空间。
为什么正确
第一遍扫到 i 时，mx 是 nums[0..i-1] 的最大值，right 是已知最右的“左边有更大数”的位置；第二遍对称。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
不能只找“第一个下降点”和“最后一个下降点”：例如 [1,3,2,2,2]，下降只发生在 3→2，但后面所有 2 都比 3 小，答案是 4。必须拿当前数和前缀最大值比较。注意相等不算乱序。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
n = len(nums)
mx, right = nums[0], -1
for i in range(n):
if nums[i] < mx:
right = i
else:
mx = nums[i]
mn, left = nums[-1], 0
for i in range(n - 1, -1, -1):
if nums[i] > mn:
left = i
else:
mn = nums[i]
return right - left + 1 if right != -1 else 0class Solution {
public int findUnsortedSubarray(int[] nums) {
int n = nums.length;
int mx = nums[0], right = -1;
for (int i = 0; i < n; i++) {
if (nums[i] < mx) {
right = i;
} else {
mx = nums[i];
}
}
int mn = nums[n - 1], left = 0;
for (int i = n - 1; i >= 0; i--) {
if (nums[i] > mn) {
left = i;
} else {
mn = nums[i];
}
}
return right != -1 ? right - left + 1 : 0;
}
}class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size();
int mx = nums[0], right = -1;
for (int i = 0; i < n; i++) {
if (nums[i] < mx) {
right = i;
} else {
mx = nums[i];
}
}
int mn = nums[n - 1], left = 0;
for (int i = n - 1; i >= 0; i--) {
if (nums[i] > mn) {
left = i;
} else {
mn = nums[i];
}
}
return right != -1 ? right - left + 1 : 0;
}
};func findUnsortedSubarray(nums []int) int {
n := len(nums)
mx, right := nums[0], -1
for i := 0; i < n; i++ {
if nums[i] < mx {
right = i
} else {
mx = nums[i]
}
}
mn, left := nums[n-1], 0
for i := n - 1; i >= 0; i-- {
if nums[i] > mn {
left = i
} else {
mn = nums[i]
}
}
if right == -1 {
return 0
}
return right - left + 1
}var findUnsortedSubarray = function(nums) {
const n = nums.length;
let mx = nums[0], right = -1;
for (let i = 0; i < n; i++) {
if (nums[i] < mx) {
right = i;
} else {
mx = nums[i];
}
}
let mn = nums[n - 1], left = 0;
for (let i = n - 1; i >= 0; i--) {
if (nums[i] > mn) {
left = i;
} else {
mn = nums[i];
}
}
return right !== -1 ? right - left + 1 : 0;
};function findUnsortedSubarray(nums: number[]): number {
const n = nums.length;
let mx = nums[0], right = -1;
for (let i = 0; i < n; i++) {
if (nums[i] < mx) {
right = i;
} else {
mx = nums[i];
}
}
let mn = nums[n - 1], left = 0;
for (let i = n - 1; i >= 0; i--) {
if (nums[i] > mn) {
left = i;
} else {
mn = nums[i];
}
}
return right !== -1 ? right - left + 1 : 0;
}其他解法
排序后对比直接看哪些位置不在最终位置；两遍扫描用前缀最大值和后缀最小值直接定位边界，省掉排序。
解法 2：排序后对比 时间 O(n log n)，空间 O(n)
复制一份数组并排序。从左往右找到第一个与排序结果不同的位置 left，从右往左找到第一个不同的位置 right。两端之外的元素已在最终位置，答案是 right − left + 1；数组本身有序时为 0。
思路直观，很容易证明正确。代价是多一个排序和一份拷贝。
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
s = sorted(nums)
n = len(nums)
left = 0
while left < n and nums[left] == s[left]:
left += 1
if left == n:
return 0
right = n - 1
while nums[right] == s[right]:
right -= 1
return right - left + 1class Solution {
public int findUnsortedSubarray(int[] nums) {
int[] s = nums.clone();
Arrays.sort(s);
int n = nums.length, left = 0;
while (left < n && nums[left] == s[left]) left++;
if (left == n) return 0;
int right = n - 1;
while (nums[right] == s[right]) right--;
return right - left + 1;
}
}class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
vector<int> s(nums);
sort(s.begin(), s.end());
int n = nums.size(), left = 0;
while (left < n && nums[left] == s[left]) left++;
if (left == n) return 0;
int right = n - 1;
while (nums[right] == s[right]) right--;
return right - left + 1;
}
};func findUnsortedSubarray(nums []int) int {
s := append([]int(nil), nums...)
sort.Ints(s)
n, left := len(nums), 0
for left < n && nums[left] == s[left] {
left++
}
if left == n {
return 0
}
right := n - 1
for nums[right] == s[right] {
right--
}
return right - left + 1
}var findUnsortedSubarray = function(nums) {
const s = [...nums].sort((a, b) => a - b);
const n = nums.length;
let left = 0;
while (left < n && nums[left] === s[left]) left++;
if (left === n) return 0;
let right = n - 1;
while (nums[right] === s[right]) right--;
return right - left + 1;
};function findUnsortedSubarray(nums: number[]): number {
const s = [...nums].sort((a, b) => a - b);
const n = nums.length;
let left = 0;
while (left < n && nums[left] === s[left]) left++;
if (left === n) return 0;
let right = n - 1;
while (nums[right] === s[right]) right--;
return right - left + 1;
}