Easy | LeetCode 581. 最短无序连续子数组 | 排序 | 单调栈 | 局部单调性

标签：数字   find   nlog   sort   条件   i+1   并且   循环   时间   

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
• -105

方法一： 暴力算法

枚举每个子序列[i, j], 枚举此子序列的时间复杂度是O(n^2), 然后找到这个子序列的最小值min和最大值max。如果子序列的前后[0, i-1] 和 [j + 1, n-1], 是升序的, 并且有 num[i-1]

所以总的时间复杂度是：O(n^3), 空间复杂度是O(1)

方法二： 暴力遍历

同样是暴力算法, 但是暴力的方法不同。遍历数组元素, 对于每个下标为i的元素nums[i], 从i后边开始遍历一遍数组, 找到比他小的元素nums[j], 如果有这个nums[i-1]小的元素, 那么, 此时的元素[i, j]都不在正确的位置, 并且[i, j]是无序连续数组的边界, 通过双重循环遍历数组的方式得到其子序列的边界。并且在此过程中, 更新边界的值。最终得到的最大的边界值, 就是最短的无序连续子数组。

public int findUnsortedSubarray(int[] nums) {
    int l = nums.length, r = 0;
    for (int i = 0; i 

这种算法的时间复杂度较第一种好, 其时间复杂度是O(n^2), 空间复杂度是O(1)

方法三： 排序

把数组重新复制一份, 并且排序。然后从两段扫描比较, 从左往右第一个同位置不等的元素就是左边界, 从右往左的第一个同位置不等的元素就是右边界。从而找到答案。

public int findUnsortedSubarray(int[] nums) {
    int[] snums = nums.clone();
    Arrays.sort(snums);
    int start = snums.length, end = 0;
    for (int i = 0; i = 0 ? end - start + 1 : 0);
}

这种算法时间复杂度时排序的时间度, 即O(nlogn), 空间复杂度是O(n), 由于需要复制数组。

方法四：单调栈

借助单调栈, 找到无序的部分的最左边界和最右边界。

从左往右扫描数组, 当前数字比栈顶元素大, 则压栈, 否则, 出栈, 知道比栈顶元素大, 这时, 找到了一个左边界, 同样的方法, 通过不断地将元素出栈, 最后栈里剩下的元素的个数就是其无序数组的左边界。

同样通过从右往左扫描数组可以得到这个数组的右边界。

public int findUnsortedSubarray(int[] nums) {
    Stack  stack = new Stack  ();
    int l = nums.length, r = 0;
    for (int i = 0; i  nums[i])
            l = Math.min(l, stack.pop());
        stack.push(i);
    }
    stack.clear();
    for (int i = nums.length - 1; i >= 0; i--) {
        while (!stack.isEmpty() && nums[stack.peek()]  0 ? r - l + 1 : 0;
}

这种时间单调栈找边界的时间复杂度是O(n), 空间复杂度也是O(n)。

方法五

从左往右扫描, 找到处于局部递减的最小元素, 其应当在的位置, 就是无序子数组的左边界。

从右往左扫描, 找到处于局部递增的最大元素, 其应当在的位置, 就是无序子数组的有边界。

public int findUnsortedSubarray(int[] nums) {
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int i = 1; i  max) {
        return 0;
    }
    
    int left = 0, right = 0;
    for (int i = 0; i  min) {
            left = i;
            break;
        }
    }
    for (int i = nums.length - 1; i >= 0; i--) {
        // 从右往左扫描数组, 找到第一个比最大值小的元素, 这个下标就是右边界
        if (nums[i] 

Easy | LeetCode 581. 最短无序连续子数组 | 排序 | 单调栈 | 局部单调性

标签：数字   find   nlog   sort   条件   i+1   并且   循环   时间   

原文地址：https://www.cnblogs.com/chenrj97/p/14327991.html