题目描述

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

你找到的子数组应是最短的，请输出它的长度。

样例

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

注意

• 输入的数组长度范围在 [1, 10000]。
• 输入的数组可能包含重复元素 ，所以升序的意思是 <=。

算法1

(排序) $O(n \log n)$

1. 将原数组拷贝一份，然后对拷贝后的数组排序。
2. 对比原数组和排序后的数组，除去前半部分和后半部分相同的数字后，剩余数字的长度就是答案。

时间复杂度

• 排序后线性扫描，故时间复杂度为 $O(n \log n)$。

C++ 代码

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        vector<int> sorted_nums(nums);

        sort(sorted_nums.begin(), sorted_nums.end());
        int i = 0;
        while (i < n && nums[i] == sorted_nums[i])
            i++;

        int j = n - 1;
        while (j >= 0 && nums[j] == sorted_nums[j])
            j--;

        return max(0, j - i + 1);
    }
};

算法2

(线性扫描) $O(n)$

线性算法的核心思路在于，将数组分为三部分，分别是起始单调递增段、中间乱序段和末尾单调递增段。需要用后两段的最小值更新起始单调递增段的结束位置，用前两段的最大值更新末尾单调递增段的起始位置。具体如下：

1. 从 0 开始向后找到第一个位置 st，使得 nums[st] < nums[st - 1]；若不存在，则 st = n。
2. 从 n - 1 开始向前寻找第一个位置 ed，使得 nums[ed] > nums[ed + 1]；若不存在，则 ed = -1。
3. 寻找 [0, ed] 的最大值 max_num 和 [st, n - 1] 的最小值 min_num。
4. 在 [0, st - 1] 这个单调递增的区间中找到第一个位置 new_st，使得 nums[new_st] > min_num。
5. 在 [ed + 1, n] 这个单调递增的区间中找到倒序找到第一个位置 new_ed，使得 nums[new_ed] < max_num。
6. 最终答案为 max(0, new_ed - new_st + 1)。

时间复杂度

• 每一步的时间复杂度都是 $O(n)$，故总时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();

        int st = n;
        for (int i = 0; i < n - 1; i++)
            if (nums[i] > nums[i + 1]) {
                st = i + 1;
                break;
            }

        int ed = -1;
        for (int i = n - 1; i >= 1; i--)
            if (nums[i - 1] > nums[i]) {
                ed = i - 1;
                break;
            }

        int max_num = INT_MIN, min_num = INT_MAX;
        for (int i = 0; i <= ed; i++)
            max_num = max(max_num, nums[i]);

        for (int i = st; i < n; i++)
            min_num = min(min_num, nums[i]);

        for (int i = 0; i < st; i++)
            if (min_num < nums[i]) {
                st = i;
                break;
            }
        for (int i = n - 1; i > ed; i--)
            if (max_num > nums[i]) {
                ed = i;
                break;
            }

        return max(0, ed - st + 1);
    }
};