2.6 最短无序连续子数组

时间复杂度O(N)，额外空间复杂度O(1)
双向遍历

🐌1. 题目描述

:::info leetcode581
给定一个数组arr，只能对arr中的一个子数组排序，但是想让arr整体都有序（升序），返回满足这一设定的子数组中最短的是多长。 ::: 示例 7，6，2，1，0，8，9
对该数组的子数组进行排序，则最短子数组为7，6，2，1，0 只需要对该子数组完成排序即可。

💡2. 解决思路

• 从左向右遍历一遍找到违反升序规则的最后一个数字的位置right
• 从右向左遍历一遍找到违反升序规则的第一个数组的位置left。
• 则left-right就是需要进行排序的最小子数组。

左侧max表示从左向右遍历的过程中指针划过区域的最大值，如果当前值>=滑过区域的最大值，则当前值肯定符合排序规则，反之违反排序规则打叉，记录最新打叉位置right，遍历完成之后得到最后一个违反的位置。 右侧min表示从右向左遍历的过程中指针划过区域的最小值，如果当前值<=划过区域的最小值，则当前值肯定符合排序规则，反之违反排序规则打叉，记录最新打叉位置left，遍历完成之后得到第一个违反的位置。

过程图：

🚩3. 代码实现

package class02;
// 本题测试链接 : https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/
public class Code06_MinLengthForSort {
    public static int findUnsortedSubarray(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int N = nums.length;
        // 从左向右遍历，找到最最后一个为叉的
        int right = -1;
        // 记录指针划过区域的最大值，
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            // 划过区域最大值>当前数，更新right
            if (max > nums[i]) {
                right = i;
            }
            max = Math.max(max, nums[i]);
        }
        // 从右向左遍历，找到最后一个为叉的
        int min = Integer.MAX_VALUE;
        int left = N;
        for (int i = N - 1; i >= 0; i--) {
            if (min < nums[i]) {
                left = i;
            }
            min = Math.min(min, nums[i]);
        }
        return Math.max(0, right - left + 1);
    }
}