【实战】单调栈经典问题-最短无序连续子数组

题意

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。

示例 1:

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

说明 :

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

思路

1. 排序比较

排序是解决这道算法题最容易理解的方法！就是将原数组拷贝一份，然后将拷贝的元素进行排序（最好不要直接在原数组上进行修改），将原数组与排序后的数组进行比较，找出最左边不匹配的元素位置 i，找出最右边不匹配的元素位置 j，两个位置之间的子数组就是要求的最短无序子数组。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] cop = nums.clone(); //将原数组拷贝一份
        Arrays.sort(cop); // 将拷贝后的数组排序

        int left = nums.length, right = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != cop[i]) {
                left = Math.min(left, i); // 找出最左边不相等的位置
                right = Math.max(right, i); // 找出最右边不相等的位置
            }
        }

        return (right > left) ? right - left + 1 : 0;
    }
}

• 时间复杂度：O(nlogn)排序消耗 nlogn 的时间；
• 空间复杂度：O(n) 拷贝了一份数组。

2. 单调栈

将此数组分成 3 段，左边有序数组 + 中间无序数组 + 右边有序数组。但要注意：要符合题意，即对这个中间这个无序的连续子数组升序排列后，整个数组都变成升序，那么“中间这个无序子数组的所有值”一定大于“右边有序数组的最大值”，一定小于“右边有序数组的最小值”。

那么我们可以从左往右遍历数组，若遇到的数字大小一直是升序的，那么就将下标不断压栈；一旦遇到一个比栈顶元素小的值，就不断将栈顶弹出，知道栈顶比该元素小。假设栈顶下标为 k，咋该元素的正确位置下标应该为 k + 1；重复这个过程直到找到最小的 k，这个值就是中间无序子数组的左边界。

同理，那么我们可以从右往左遍历数组，若遇到的数字大小一直是降序的，那么就将下标不断压栈；一旦遇到一个比栈顶元素大的值，就不断将栈顶弹出，直到栈顶比该元素大。假设栈顶下标为 k，则该元素的正确位置下标应该为 k - 1；重复这个过程直到找到最大的 k，这个值就是中间无序子数组的右边界。

class Solution {

       public int findUnsortedSubarray(int[] nums) {
        Deque<Integer> stack = new LinkedList<>();

        int left = nums.length, right = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                left = Math.min(left, stack.pop());
            }
            stack.push(i);
        }
        for (int i = nums.length - 1; i > 0; i--) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                right = Math.max(right, stack.pop());
            }
            stack.push(i);
        }

        return right > left ? right - left + 1: 0;
    }

}

• 时间复杂度：O(n)；
• 空间复杂度：O(n)。

3. 多次遍历确定边界

无序子数组中最小元素的正确位置可以用来确定左边界，无序子数组中的最大元素的正确位置可以用来确定右边界。

因此，我们需要找到原数组在哪个位置开始不是升序的。我们从头开始遍历数组，一旦遇到降序的元素，我们记录最小元素为 min。同样我们逆序扫描数组，当数组出现升序的时候，我们记录最大元素为 max。

然后，我们再次遍历数组并通过与其他元素进行比较，来找到 min 和 max 在原数组中的正确位置。我们只需要从头开始找到第一个大于 min 的元素，从尾开始找到第一个小于 max 的元素，它们之间就是最短无序子数组。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        boolean flag = false;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) { // 标志出现降序
                flag = true;
            }
            if (flag = true) {
                min = Math.min(min, nums[i]);
            }
        }

        flag = false;
        for (int i = nums.length - 2; i >= 0; i++) {
            if (nums[i] > nums[i + 1]) { // 标志出现降序
                flag = true;
            }
            if (flag = true) {
                max = Math.max(max, nums[i]);
            }
        }

        int left = nums.length, right = 0;
        for (int i = 0; i < nums.length; i++) {

        }
    }
}