题目描述

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

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

示例 1：

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

算法思路

这个题目难在要求$O(N)$的复杂度，如果没有这个要求，那么直接排序一遍然后比对改变的那一段区间即可，比如题目这个示例，排序后是[2, 4, 6 , 8, 9, 10, 15]，相比起来只有[6, 4, 8, 10, 9]变了，所以长度为5。但是要求为$O(N)$的话必然是不可以排序了。

我们注意到一个问题，如果把原始的数组分成三部分numsa, numsb, numsc，那么numsa, numc必然是有序且升序的，例如示例的[2, 6], [9, 15]，问题出现在左侧遍历到4时，发现比6要小，不满足升序，说明至少从6开头的这一段数组出问题了，右侧我们采用倒序方式遍历，本应该是降序的，但同样发现[10, 9]有问题，因此我们的目标就是：找到一个左边界，一个右边界，能够涵盖住出现问题的数组部分，现在的关键就是确定哪一部分数组需要重排，很显然，遇到4后，我们需要把4排到6的左侧，但是一定是6的紧邻左侧吗？并不是，我们需要找到6左侧一个第一个小于4的数，比如这个2，满足2->4->6是升序才可以，不然如果出现5,6,4: 5->4->6并不满足题意。同理右侧也需要这样处理，找到10右侧第一个大于10的数。这样的话我们只需要排序2->......<-15即可。

其实光这样处理还是不够，因为我们没有考虑左右边界的关系，我们上面的推论建立在右边界的数一定大于左边界的基础上（15>2），但是如果是这样的情况nums=[1, 3, 5, 4, 2]，那按照我们的处理方式只需要排序3->......<-2，得到的结果是[1, 3, 4, 5, 2]，并没有考虑2,3是否需要排序，因此我们还需要考虑到这一点；

另外，左边界必须要小于”被排序数组中最小的数”， 右边界必须要大于“被排序数组中最大的数”，这个很好理解，不再解释。因此考虑以上三点，综合得到的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int result = 0;
        int l;
        for (l = 1; l < n; l++) {
            if (nums[l] < nums[l-1]) {
                break;
            }
        }
        if (l != n) {
            // 找到一个下坡拐点
            int start = l - 1;
            while (start >= 0) {
                if (nums[start] <= nums[l]) {
                    break;
                }
                start--;
            }
            start = start>=0 ? start : 0; // 最左侧


            int r;
            for (r = n - 2; r >= start; r--) {
                if (nums[r] > nums[r+1]) {
                    break;
                }
            }
            int end = r + 1;
            while (end < n) {
                if (nums[end] >= nums[r]) {
                    break;
                }
                end ++;
            }
            end = end < n ? end : n - 1; // 最右侧

            int min_e = *min_element(nums.begin() + start, nums.begin() + end + 1);
            int max_e = *max_element(nums.begin() + start, nums.begin() + end + 1);

            while (start >= 0 && nums[start] > min_e) {
                start--;
            }
            start++;

            while (end < n && nums[end] < max_e) {
                end++;
            }
            end--;


            result = end - start + 1;
        }
        return result;
    }
};