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

mood321 · mood321 · commit 052d87beebd7 · 2021-12-16T00:24:43.000+08:00
diff --git a/src/main/java/algorithm/Interview/practice08/P_8_4_GetMinLength.java b/src/main/java/algorithm/Interview/practice08/P_8_4_GetMinLength.java
@@ -0,0 +1,43 @@
+package algorithm.Interview.practice08;
+
+/**
+ * @author mood321
+ * @date 2021/12/16 0:04
+ * @email 371428187@qq.com
+ */
+public class P_8_4_GetMinLength {
+    public static void main(String[] args) {
+        int[] ints={1,5,3,4,2,6,7};
+        int minlength = getMinlength(ints);
+        System.out.println(minlength);
+    }
+    public static int getMinlength(int[] arr) {
+        if (arr == null || arr.length == 0) {
+            return 0;
+        }
+        //
+        int min = arr[arr.length - 1];
+        int minIdx = -1;
+        for (int i = arr.length - 1; i >= 0; i--) {
+            if (arr[i] < min) {
+                min = Math.min(arr[i], min);
+            } else {
+                minIdx = i;
+            }
+
+        }
+        if (minIdx == -1) {
+            return 0;
+        }
+        int max = arr[0];
+        int maxIdx = -1;
+        for (int i = 1; i < arr.length; i++) {
+            if (arr[i] < max) {
+                maxIdx = i;
+            } else {
+                max=Math.max(arr[i],max);
+            }
+        }
+        return  maxIdx-minIdx +1;
+    }
+}
diff --git a/src/main/resources/note/Algorithm/程序员面试.md b/src/main/resources/note/Algorithm/程序员面试.md
@@ -1090,6 +1090,44 @@ N皇后问题是指N*N的棋盘要摆N个皇后，要求任何两个皇后不同
 <p><a href="/src/main/java/algorithm/Interview/practice08/P_8_3_MinNumK.java"> code</a>
     
 
+    
+````
+
+4  找到需要排序的最短子数组长度
+
+【题目】
+题目描述：对于一个无序数组A，请设计一个算法，求出需要排序的最短子数组的长度。 给定一个整数数组A及它的大小n，请返回最短子数组的长度。
+要求：时间复杂度O(n) 空间复杂度O(1)
+例子： [1,5,3,4,2,6,7]
+返回：4
+ 
+
+【要求】
+
+　 O(NlogK)
+【进阶】
+
+　 O(N)
+　　
+　　
+【基本思路】
+
+ 思路 1:  1. 从左往右找”当前值比max小”的一系列情况：
+初始：max=arr[0]；
+如果当前元素比max大，max就等于当前元素；
+如果当前元素比max小，max不变，然后继续往后找,直到最后一次出现”当前值比max小”的情形，记下此时的下标为k。
+2. 从右往左找”当前值比min大”的一系列情况：
+初始：min=arr[6];
+如果当前元素比min小，min就等于当前元素；
+如果当前元素比min大，min不变，然后继续往前找，直到最后一次出现就”当前值比min大”的情形，记下此时的下标为j。
+3. 长度=k-j+1。
+ 
+ 循环一次搞定
+ 
+````
+<p><a href="/src/main/java/algorithm/Interview/practice08/P_8_3_MinNumK.java"> code</a>
+    
+
 
 
 ### 其他
