这道题目感觉并不太容易，也并没有想到什么比较好的方法，看来还是积累太少。

 

思路一：两个指针向后遍历，分别记下造成逆序的最小和最大下标位置

优化的暴力解法（很精妙，面试的时候可以说出来）

思想：两个指针向后遍历，后面的比前面的大时，分别记录这两个元素的下标 lo 和 hi，前面的下标是造成逆序的第一个元素所以我们记录它，它也一直是后面逆序出现位置的最小值。二而后面的元素更新一直都表示构成元素逆序的最大下标位置。

最后 hi-lo+1就是 最小的那个子数组。

【正确代码】

1 public class Solution { 2     public int findUnsortedSubarray(int[] nums) { 3         int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE; 4         for (int i = 0; i < nums.length; i++) { 5             for (int j = i; j < nums.length; j++) { 6                 if (nums[j] < nums[i]) { 7                     lo = Math.min(lo, i); 8                     hi = Math.max(hi, j); 9                 }10             }11         }12         return hi - lo < 0 ? 0 : hi - lo + 1;13     }14 }

复杂度分析

时间复杂度：O(n^2)

空间复杂度：o(1)

 

思路二：和排序后的比较，找出前后第一个不相等的数字，计算下标差

【正确代码】

1 public class Solution { 2     public int findUnsortedSubarray(int[] nums) { 3         int[] sortNums = new int[nums.length]; 4         System.arraycopy(nums, 0, sortNums, 0, nums.length); 5         Arrays.sort(sortNums); 6         int lo = nums.length - 1, hi = 0; 7         int i = 0, j = nums.length - 1; 8         while (i < nums.length - 1) { 9             if (sortNums[i] != nums[i]) {10                 lo = i;11                 break;12             }13             i++;14         }15         while (j > 0) {16             if (sortNums[j] != nums[j]) {17                 hi = j;18                 break;19             }20             j--;21         }22         return hi - lo <= 0 ? 0 : hi - lo + 1;23     }24 }

 

复杂度分析

时间复杂度：O(n*logn) 主要消耗在排序

空间复杂度：O(n) 申请了空间

 

思路三：使用stack，从前向后压栈，找到第一个下降的元素，并记录下标。同理，从后向前，找到第一个上升元素，并记录下标，最后计算下标差即可。

第一次写时出现错误，没有考虑到等于的情况。

【错误代码】

1 public class Solution { 2     public int findUnsortedSubarray(int[] nums) { 3         Stack
     
       stack = new Stack<>(); 4         int lo = 0, hi = 0; 5         one: { 6             for (int i = 0; i < nums.length; i++) { 7                 while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) { //stack 中元素大于新添加元素 8                     lo = stack.peek(); 9                     break one;10                 }11                 stack.push(i);12             }13         }14         stack.clear();15         two: {16             for (int i = nums.length - 1; i >= 0; i--) {17                 while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {18                     hi = stack.peek();19                     break two;20                 }21                 stack.push(i);22             }23         }24         25         return hi - lo <= 0 ? 0 : hi - lo + 1;26     }27 }
     

【错误输出】

Input:[1,3,2,2,2]

Output:2

Expected:4

【分析错误原因】

不要随意使用break，蓝色处很重要只要比栈顶大就一只向外弹出。改正代码如下：

【正确代码】

1 class Solution { 2     public int findUnsortedSubarray(int[] nums) { 3         Stack
     
       stack = new Stack<>(); 4         int lo = nums.length - 1; 5         int hi = 0; 6         for (int i = 0; i < nums.length; i++) { 7             while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) { 8                 lo = Math.min(lo, stack.pop()); 9             }10             stack.push(i);11         }12         stack.clear();13         for (int j = nums.length -1; j >= 0; j--) {14             while (!stack.isEmpty() && nums[j] > nums[stack.peek()]) {15                 hi = Math.max(hi, stack.pop());16             }17             stack.push(j);18         }19         return hi - lo > 0 ? hi - lo + 1 : 0;20     }21 }
     

复杂度分析

时间复杂度：O(n) 

空间复杂度：O(n) stack的深度

 

思路四：从前往后找，从前面比后面小的数中，找到并保存其中最小的数，之后再从前向后找，找出第一个大于这个数的下标即为所求。后面同理。