需要排序的最短子数组长度

题目：给定一个无序数组长度arr，求出需要排序的最短子数组长度。如输入：arr={2,3,7,5,4,6}，返回4，因为只有{7,5,4,6}需要排序。注意这儿题目是要求数组按照递增排序。

代码：

 1 public class Rearrange {
 2     public static int findSegment(int[] A, int n) {
 3         // p1 p2为需要排序的子数组边界
 4         int p1 = -1;
 5         int p2 = -1;
 6         int max = A[0];
 7         int min = A[n - 1];
 8         //拓展右端点：更新历史最高，只要右侧出现比历史最高低的，就应该将右边界扩展到此处
 9         for (int i = 0; i < n; i++) {
10           if (A[i] > max) {
11             max = A[i];
12           }
13           //只要低于历史高峰，就要扩展需排序区间的右端点
14           if (A[i] < max)
15             p2 = i;
16         }
17         //找左端点：更新历史最低，只要左侧出现比历史最低高的，就应该将左边界扩展到此处
18         for (int i = n - 1; i >= 0; i--) {
19 
20           if (A[i] < min) {
21             min = A[i];
22           }
23           if (A[i] > min)
24             p1 = i;
25         }
26 
27         if (p1 == -1) {
28           return -1;
29         }
30         // p1 p2为需要排序的子数组边界 所以应该返回长度 p2-p1+1
31         return p2-p1+1;
32       }
33     public static void main(String[] args) {
34         int res = findSegment(new int[]{2,3,7,5,4,6}, 6);
35         System.out.println(res);   // 输出 4
36     }
37 }

总结：拿到这种题目，需要仔细分析，然后发现规律，并且在分析的过程中要考虑各种测试用例，小数据、大数据、反例、边界数据、时间复杂度等等。那这道题目本身没有什么算法可言，只有自己去寻找规律解决。