• LeetCode581:最短无序连续子数组


    要求

    给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。

    请你找出符合题意的 最短 子数组,并输出它的长度。

    在这里插入图片描述

    思路

    我们可以假设把这个数组分成三段,左段和右段是标准的升序数组,中段数组虽是无序的,但满足最小值大于左段的最大值,最大值小于右段的最小值。
    那么我们目标就很明确了,找中段的左右边界,我们分别定义为 L 和 R;

    先只考虑中段数组,设其左边界为L,右边界为R:

    • nums[R] 不可能是【L,R】中的最大值(否则应该将 nums[R] 并入右端数组)
    • nums[L] 不可能是【L,R】中的最小值(否则应该将 nums[L] 并入左端数组)

    很明显:

    • 【L,R】中的最大值 等于【0,R】中的最大值,设其为 max
    • 【L,R】中的最小值 等于 【L, nums.length-1】中的最小值,设其为 min

    那么有:

    • nums[R] < max < nums[R+1] < nums[R+2] < … 所以说,从左往右遍历,最后一个小于max的为右边界
    • nums[L] > min > nums[L-1] > nums[L-2] > … 所以说,从右往左遍历,最后一个大于min的为左边界
    public class LeetCode581 {
        public int findUnsortedSubarray(int[] nums) {
            //右边界从左往右遍历;左边界从右往左遍历
            int max = nums[0];
            int min = nums[nums.length - 1];
            int L = 0,R = -1;
    
            for (int i = 1; i < nums.length; i++) {
                //左 ---> 右;寻找[0,R]最大值为max,最后一个小于max的为右边界
                if (max <= nums[i]){
                    max = nums[i];
                }else {
                    R = i;
                }
    
                //右 ---> 左;寻找[L,nums.length-1]min,最后一个大于min的为左边界
                if (min >= nums[nums.length - i - 1]){
                    min = nums[nums.length - i -1];
                }else {
                    L = nums.length - i - 1;
                }
            }
            return R - L + 1;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    R右边界需要初始化为-1,要不完美的输入不需要调整,返回+1会出问题
    在这里插入图片描述

  • 相关阅读:
    markdown math语法
    斩获 offer 的 Java 面试宝典
    关于Linux搭建DedeCMS说明
    21天学习第十一天-Set集合
    2022年Java秋招面试必看的 | RabbitMQ 面试题
    [计算机提升] 计算机系统中的格式化
    凉鞋的 Godot 笔记 104. 测试所涉及的窗口
    【基础算法】圆周率的多种方法求算 & C++实现
    MySQL(4)
    spring boot项目使用mybatis连接失败问题
  • 原文地址:https://blog.csdn.net/weixin_46426906/article/details/127663846