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

题目描述

这是 LeetCode 上的 581. 最短无序连续子数组 ，难度为 中等。

给你一个整数数组 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

提示：

• 1 <= nums.length <= $10^4$

• -$10^5$ <= nums[i] <= $10^5$

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

---

双指针 + 排序

最终目的是让整个数组有序，那么我们可以先将数组拷贝一份进行排序，然后使用两个指针 $i$ 和 $j$ 分别找到左右两端第一个不同的地方，那么 $[i, j]$ 这一区间即是答案。

代码：

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int i = 0, j = n - 1;
        while (i <= j && nums[i] == arr[i]) i++;
        while (i <= j && nums[j] == arr[j]) j--;
        return j - i + 1;
    }
}

• 时间复杂度：$O(n\log{n})$
• 空间复杂度：$O(n)$

---

双指针 + 线性扫描

另外一个做法是，我们把整个数组分成三段处理。

起始时，先通过双指针 $i$ 和 $j$ 找到左右两次侧满足 单调递增 的分割点。

即此时 $[0, i]$ 和 $[j, n)$ 满足升序要求，而中间部分 $(i, j)$ 不确保有序。

然后我们对中间部分 $[i, j]$ 进行遍历：

• 发现 $nums[x] < nums[i - 1]$：由于对 $[i, j]$ 部分进行排序后 $nums[x]$ 会出现在 $nums[i - 1]$ 后，将不满足整体升序，此时我们需要调整分割点 $i$ 的位置；
• 发现 $nums[x] > nums[j + 1]$：由于对 $[i, j]$ 部分进行排序后 $nums[x]$ 会出现在 $nums[j + 1]$ 前，将不满足整体升序，此时我们需要调整分割点 $j$ 的位置。

一些细节：在调整 $i$ 和 $j$ 的时候，我们可能会到达数组边缘，这时候可以建立两个哨兵：数组左边存在一个足够小的数，数组右边存在一个足够大的数。

代码：

class Solution {
    int MIN = -100005, MAX = 100005;
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int i = 0, j = n - 1;
        while (i < j && nums[i] <= nums[i + 1]) i++;
        while (i < j && nums[j] >= nums[j - 1]) j--;
        int l = i, r = j;
        int min = nums[i], max = nums[j];
        for (int u = l; u <= r; u++) {
            if (nums[u] < min) {
                while (i >= 0 && nums[i] > nums[u]) i--;
                min = i >= 0 ? nums[i] : MIN;
            }
            if (nums[u] > max) {
                while (j < n && nums[j] < nums[u]) j++;
                max = j < n ? nums[j] : MAX;
            }
        }
        return j == i ? 0 : (j - 1) - (i + 1) + 1;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.581 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。