題目及測試
package pid581;
/*581. 最短無序連續子數組
給定一個整數數組，你需要尋找一個連續的子數組，如果對這個子數組進行升序排序，那麼整個數組都會變為升序排序。
你找到的子數組應是最短的，請輸出它的長度。
示例 1:
輸入: [2, 6, 4, 8, 10, 9, 15]
輸出: 5
解釋: 你隻需要對 [6, 4, 8, 10, 9] 進行升序排序，那麼整個表都會變為升序排序。
說明 :
輸入的數組長度範圍在 [1, 10,000]。
輸入的數組可能包含重複元素 ，是以升序的意思是<=。
*/
public class main {
public static void main(String[] args) {
int[][] testTable = {{1,1,2},{1,1,2,2,5,6,7,7},{1,2,3,5},{1,1,1,1}};
for (int[] ito : testTable) {
test(ito);
}
}
private static void test(int[] ito) {
Solution solution = new Solution();
int rtn;
long begin = System.currentTimeMillis();
for (int i = 0; i < ito.length; i++) {
System.out.print(ito[i]+" ");
}//開始時列印數組
rtn = solution.findUnsortedSubarray(ito);//執行程式
long end = System.currentTimeMillis();
System.out.println("rtn=" + rtn);
/*for (int i = 0; i < rtn; i++) {
System.out.print(ito[i]+" ");
}//列印結果幾數組
*/ System.out.println();
System.out.println("耗時：" + (end - begin) + "ms");
System.out.println("-------------------");
}
}
沒想出來
解法1（别人的）
使用棧
這個方法背後的想法仍然是選擇排序。我們需要找到無序子數組中最小元素和最大元素分别對應的正确位置，來求得我們想要的無序子數組的邊界。
為了達到這一目的，此方法中，我們使用 棧棧棧 。我們從頭周遊 nums 數組，如果遇到的數字大小一直是升序的，我們就不斷把對應的下标壓入棧中，這麼做的目的是因為這些元素在目前都是處于正确的位置上。一旦我們遇到前面的數比後面的數大，也就是 nums[j] 比棧頂元素小，我們可以知道 nums[j] 一定不在正确的位置上。
為了找到 nums[j] 的正确位置，我們不斷将棧頂元素彈出，直到棧頂元素比 nums[j] 小，我們假設棧頂元素對應的下标為 k ，那麼我們知道 nums[j] 的正确位置下标應該是 k+1 。
我們重複這一過程并周遊完整個數組，這樣我們可以找到最小的 k， 它也是無序子數組的左邊界。
類似的，我們逆序周遊一遍 nums 數組來找到無序子數組的右邊界。這一次我們将降序的元素壓入棧中，如果遇到一個升序的元素，我們像上面所述的方法一樣不斷将棧頂元素彈出，直到找到一個更大的元素，以此找到無序子數組的右邊界。
我們可以看下圖作為參考。我們觀察到上升還是下降決定了相對順序，我們還可以觀察到指針 b 在下标 0 後面标記着無序子數組的左邊界，指針 a 在下标 7 前面标記着無序子數組的右邊界。
public class Solution {
public int findUnsortedSubarray(int[] nums) {
Stack < Integer > stack = new Stack < Integer > ();
int l = nums.length, r = 0;
for (int i = 0; i < nums.length; i++) {
while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
l = Math.min(l, stack.pop());
stack.push(i);
}
stack.clear();
for (int i = nums.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
r = Math.max(r, stack.pop());
stack.push(i);
}
return r - l > 0 ? r - l + 1 : 0;
}
}
解法2（别人的）
不使用額外空間
這個算法背後的思想是無序子數組中最小元素的正确位置可以決定左邊界，最大元素的正确位置可以決定右邊界。
是以，首先我們需要找到原數組在哪個位置開始不是升序的。我們從頭開始周遊數組，一旦遇到降序的元素，我們記錄最小元素為 min 。
類似的，我們逆序掃描數組 nums，當數組出現升序的時候，我們記錄最大元素為 max。
然後，我們再次周遊 nums 數組并通過與其他元素進行比較，來找到 min 和 max 在原數組中的正确位置。我們隻需要從頭開始找到第一個大于 min 的元素，從尾開始找到第一個小于 max 的元素，它們之間就是最短無序子數組。
public class Solution {
public int findUnsortedSubarray(int[] nums) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
boolean flag = false;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1])
flag = true;
if (flag)
min = Math.min(min, nums[i]);
}
flag = false;
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] > nums[i + 1])
flag = true;
if (flag)
max = Math.max(max, nums[i]);
}
int l, r;
for (l = 0; l < nums.length; l++) {
if (min < nums[l])
break;
}
for (r = nums.length - 1; r >= 0; r--) {
if (max > nums[r])
break;
}
return r - l < 0 ? 0 : r - l + 1;
}
}