一、题目

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

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

点击查看原题
难度级别：中等

二、思路

暴力方法就是将数组进行排序，然后从两端扫描，与排序之前的数组进行对比，就可以找到需要进行排序的最短子数组

1）单调性判断+一次扫描

根据官方题解，先讲解概念，将数组分为连续的三个部分，numsa、numsb、numsc，其中numsa为有序的最小部分、numsb为需要排序的最短子数组、numsc为有序的高位部分，numsa中的任意元素小于另外两个部分的所有元素，numsc中任意元素大于另外两个部分的所有元素。
numsb的两端分别讨论：
右端，也就是right，numsb必定存在一个位置i，使得nums[i]>nums[right]（因为如果不存在i的话，nums[right]为numsb中最大值，可以归类到numsc中去了），思路：从左向右遍历，找到最大值nums[i]，当nums[i]>nums[j]时，right=j
左端，left，numsb中必定存在一个位置i，使得nums[i]<nums[left]（同理），思路：从右向左遍历，找到最小值nums[i]，当nums[i]<nums[j]时，left=j

三、代码

1）单调性判断+一次扫描

  1. class Solution {
  2.     public int findUnsortedSubarray(int[] nums) {
  3.         int maxn = Integer.MIN_VALUE, right = -1;
  4.         int minn = Integer.MAX_VALUE, left = -1;
  5.         for (int i = 0; i < nums.length; i++) {
  6.             if (maxn <= nums[i]) {
  7.                 maxn = nums[i];
  8.             } else {
  9.                 right = i;
  10.             }
  11.             if (minn >= nums[nums.length - 1 - i]) {
  12.                 minn = nums[nums.length - 1 - i];
  13.             } else {
  14.                 left = nums.length - 1 - i;
  15.             }
  16.         }
  17.         return right == -1 ? 0 : right - left + 1;
  18.     }
  19. }

时间复杂度为O(n)，空间复杂度为O(1)