最短无序子数组

给你一个整数数组 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 <= 104
-105 <= nums[i] <= 105

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

从右往左找到有序的位置，从左往右找到有序的位置。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        int right = 0, left = n - 1;

        for (int i = 0; i < n; i++) {
            if (max > nums[i]) {
                // 到i时右边还是大于左边的（也就是有序的）
                right = i;
            } else {
                max = nums[i];
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            if (min < nums[i]) {
                // 到i时左边还是小于右边的（也就是有序的）
                left = i;
            } else {
                min = nums[i];
            }
        }
        if (right > left) {
            return right - left + 1;
        } else {
            return 0;
        }
    }
}

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        boolean flag = false;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1])
                flag = true;
            if (flag)
                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)
                max = Math.max(max, nums[i]);
        }
        int l, r;
        for (l = 0; l < nums.length; l++) {
            if (min < nums[l])
                break;
        }
        for (r = nums.length - 1; r >= 0; r--) {
            if (max > nums[r])
                break;
        }
        return r - l < 0 ? 0 : r - l + 1;
    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/zui-duan-wu-xu-lian-xu-zi-shu-zu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

从左到右循环，记录最大值为 max，若 nums[i] < max, 则表明位置 i 需要调整, 循环结束，记录需要调整的最大位置 i 为 high; 同理，从右到左循环，记录最小值为 min, 若 nums[i] > min, 则表明位置 i 需要调整，循环结束，记录需要调整的最小位置 i 为 low.

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
	if(len <= 1) return 0;
	int high = 0, low = len-1, max = nums[0], min = nums[len-1];
	for(int i = 1; i < len; i++){
	    max = Math.max(max, nums[i]);
	    min = Math.min(min, nums[len-1-i]);
	    if(nums[i] < max) high = i;
	    if(nums[len-1-i] > min) low = len-1-i;
	}
	return high > low ? high - low + 1 : 0;
    }
}

xyt的评论

赏

谢谢你请我吃糖果

微信