夯实算法-最短无序连续子数组

题目：LeetCode

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

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

示例 1：

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

示例 2：

输入： nums = [1,2,3,4]
输出： 0
复制代码

示例 3：

输入： nums = [1]
输出： 0
复制代码

提示：

• <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo><</mo><mo>=</mo><mi>n</mi><mi>u</mi><mi>m</mi><mi>s</mi><mi mathvariant="normal">.</mi><mi>l</mi><mi>e</mi><mi>n</mi><mi>g</mi><mi>t</mi><mi>h</mi><mo><</mo><mo>=</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">1 <= nums.length <= 10^4</annotation></semantics></math>1<=nums.length<=104
• <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>−</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup><mo><</mo><mo>=</mo><mi>n</mi><mi>u</mi><mi>m</mi><mi>s</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo><</mo><mo>=</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">-10^5 <= nums[i] <= 10^5</annotation></semantics></math>−105<=nums[i]<=105

解题思路

按题意，最短无序子数组可以把整个数组分成三个部分，第一部分是有序的，第二部分是无序子数组，第三部分仍是有序的。

如示例1，第1部分为[2]，第二部分（即答案)是[6,4,8,10,9]，第3部分是[15]。

若能找到边界，那么就能划分出这三个部分。左边界left，一定能是[left]>[left+1]，而右边一定满足[right−1]>[right]。因为对于有序的话，一定都是[i]<[i+1]的。

可以分别查找left，且注意当left到达n−1时，说明数组是升序的；同理查找right时如果right到达0时，说明也是升序的。

这样，left 会指向左边第一个乱序的元素，right 指向右边第一个乱序，right−left+1 即是个数。

但还要注意，要想把第二部分排序后整体是升序，那么第二部分的所有元素要大于等于第一部分，同时要小于等于第三部分，这是一个很重要的隐含条件，相信大部分人会在此WA（包括我）。

需要找到[left,right]之间的最大值和最小值，如果[left−1]大于min，就需要向左扩；如果[right+1]小于最大值，就需要向右扩。

代码实现

public int findUnsortedSubarray(int[] nums) {
    int n = nums.length;
    if (n == 1) {
        return 0;
    }
    int left = 0;
    while (left < n - 1) {
        if (nums[left] > nums[left + 1]) {
            break;
        }
        left++;
    }
    if (left == n - 1) {
        return 0;
    }
    int right = n - 1;
    while (right > 0) {
        if (nums[right] < nums[right - 1]) {
            break;
        }
        right--;
    }
    if (right == 0) {
        return 0;
    }
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int i = left; i <= right; i++) {
        if (min > nums[i]) {
            min = nums[i];
        }
        if (max < nums[i]) {
            max = nums[i];
        }
    }
    while (left > 0 && nums[left - 1] > min) {
        left--;
    }
    while (right < n - 1 && nums[right + 1] < max) {
        right++;
    }
    return right - left + 1;
}
复制代码

复杂度分析

• 空间复杂度：<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1)
• 时间复杂度：<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math>O(n)