Leetcode 581.最短无序连续子数组


题目描述:

给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组,并输出它的长度。

进阶:你可以设计一个时间复杂度为 O(n) 的解决方案吗?

示例 1:

1
2
3
输入:nums = [2,6,4,8,10,9,15]
输出:5
解释:你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。

示例 2:

1
2
输入:nums = [1,2,3,4]
输出:0

示例 3:

1
2
输入:nums = [1]
输出:0

提示:

  • $1 <= nums.length <= 10^4$
  • $-10^5 <= nums[i] <= 10^5$

链接:

https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray


题目分析

  这个子数组将原数组分成了三段,左边和右边都是排好序的数组,并且要满足这三段中的任意数都有大小关系。也就是说中间的任一个数都比左边的大。进阶要求提示我们应该使用遍历就可以完成,如何在遍历中找到分割数组的端点呢?
  我们先考虑左边,如果是按照从右到左的遍历顺序维护一个最小值,那么在左边的数组中,应该可以不断更新最小值,而最后一个不满足这样性质的就是左端点。我们使用一个例子来辅助理解。比如我们有这样一个数组 [1,2,3,5,6,4,9,7,8,10,11,12],分割的区间应该是 [5 ~ 8]。先观察一下左端点 5 的性质,它其实仍然是大于 3 的,但是它比 4 大,所以已经属于中间的数组了,我们从右向左遍历,遍历到 4 的时候就记录到了最小值 4,而遍历到 5 的时候可以将左端点记录为 5(因为它比 4 大),而继续遍历 321 的时候则是不断更新最小值,那么更新最小值的时候就可以不用更新左端点。
  上面的分析中,从右到左遍历可以获得左端点,那同理从左到右遍历应该可以获得右端点。并且获得左端点是维护最小值,获得右端点是维护最大值,这两个过程是不冲突的,可以同时进行的,那么我们只使用一趟遍历就可以了。
  最后再考虑一下边界情况。如果数组最开始就是有序的,那么我们应该找不到左右端点,这个时候左右端点就是初始值,而返回结果应该是 0。另一种是数组中也可能出现同数字,这个时候要更新最值还是更新端点呢?我们考虑 [1,3,2,4,4] 这样的数组,它的分割区间应该是 [3,2],从左到右遍历时,遍历到第二个 4 的时候,它与当前最大值相同,这个时候右端点不应该更新,而它与最大值相同,更新最大值是不会产生任何影响的。所以我们应该将等于最值的情况归为更新最值的办法中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size();
int left = -1, right = -1;
int minn = INT_MAX, maxn = INT_MIN;
for(int i = 0; i < n; i++){
if(nums[i] >= maxn){
maxn = nums[i];
}
else{
right = i;
}
if(nums[n - i - 1] <= minn){
minn = nums[n - i - 1];
}
else{
left = n - i - 1;
}
}
return left == right ? 0 : right - left + 1;
}
};

  时间复杂度:$O(n)$,其中 $n$ 是数组的大小。我们只需要对数组进行一次遍历。
  空间复杂度:$O(1)$。我们只需要常数个变量的空间。