題目

題解

方法1（暴力排序）：時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(n)

一個(gè)簡(jiǎn)單的想法是：將數(shù)組 nums 進(jìn)行排序，記為 nums_sorted 。然后比較 nums 和 nums_sorted 的元素來(lái)決定最左邊和最右邊不匹配的元素。它們之間的子數(shù)組就是要求的最短無(wú)序子數(shù)組。

public int findUnsortedSubarray(int[] nums) {int[] snums = nums.clone();Arrays.sort(snums);int start = snums.length, end = 0;for (int i = 0; i < snums.length; i++) {if (snums[i] != nums[i]) {start = Math.min(start, i);end = Math.max(end, i);}}return (end - start >= 0 ? end - start + 1 : 0); }

方法2（單調(diào)棧思想）：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)

我們需要找到無(wú)序子數(shù)組中 最小元素 和 最大元素 分別對(duì)應(yīng)的 正確位置，來(lái)求得我們想要的無(wú)序子數(shù)組的邊界。

為了達(dá)到這一目的，此方法中，我們使用 單調(diào)棧結(jié)構(gòu)。

我們從頭遍歷 nums 數(shù)組，如果遇到的數(shù)字大小一直是升序的，我們就不斷把對(duì)應(yīng)的下標(biāo)壓入棧中，這么做是因?yàn)檫@些元素在目前都是 處于正確的位置上。一旦我們遇到 前面的數(shù)比后面的數(shù)大，也就是 nums[j] 比棧頂元素小，我們可以知道 nums[j] 一定不在正確的位置上。為了找到 nums[j] 的正確位置，我們 不斷將棧頂元素彈出，直到棧頂元素比 nums[j] 小，我們假設(shè)棧頂元素對(duì)應(yīng)的下標(biāo)為 k ，那么我們知道 nums[j] 的正確位置下標(biāo)應(yīng)該是 k+1 。

我們重復(fù)這一過(guò)程，直到遍歷完整個(gè)數(shù)組，這樣我們可以找到 最小的 k， 它就是 無(wú)序子數(shù)組的左邊界。

（實(shí)際上：所謂左邊界，就是 “所有未在正確位置的數(shù)當(dāng)中最小的那個(gè)” 的正確位置，在數(shù)值上等同于 “所有的左邊界當(dāng)中最小的左邊界”。同樣地，所謂右邊界，就是 “所有未在正確位置的數(shù)當(dāng)中最大的那個(gè)” 的正確位置，在數(shù)值上等同于 “所有的右邊界當(dāng)中最大的右邊界”。）

類似地，我們逆序遍歷一遍 nums 數(shù)組來(lái)找到無(wú)序子數(shù)組的 右邊界。這一次我們將降序的元素壓入棧中，如果遇到一個(gè)升序的元素，我們像上面所述的方法一樣不斷將棧頂元素彈出，直到找到一個(gè)更大的元素，以此找到無(wú)序子數(shù)組的右邊界。

我們可以看下圖作為參考。從圖中可以觀察到，上升還是下降決定了相對(duì)順序；還可以觀察到，指針 b 指向所有未在正確位置的數(shù)當(dāng)中的最小的那個(gè)，它在下標(biāo) 0 后面標(biāo)記著 “無(wú)序子數(shù)組中最小的左邊界” 1；指針 a 指向所有未在正確位置的數(shù)當(dāng)中的最大的那個(gè)，它在下標(biāo) 7 前面標(biāo)記著 “無(wú)序子數(shù)組中最大的右邊界” 6。

public static int findUnsortedSubarray(int[] nums) {Stack<Integer> stack = new Stack<Integer>(); // 單調(diào)棧int left = nums.length; // 左邊界int right = 0; // 右邊界for (int i = 0; i < nums.length; i++) { // 找到左邊界while (!stack.isEmpty() && nums[stack.peek()] > nums[i])left = Math.min(left, stack.pop()); // 取所有的左邊界當(dāng)中最小的左邊界stack.push(i);}stack.clear();for (int i = nums.length - 1; i >= 0; i--) { // 找到右邊界while (!stack.isEmpty() && nums[stack.peek()] < nums[i])right = Math.max(right, stack.pop()); // 取所有的右邊界當(dāng)中最大的右邊界stack.push(i);}return right - left > 0 ? right - left + 1 : 0; }

方法3（進(jìn)階）：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

同時(shí)從前往后和從后往前遍歷，分別得到要排序數(shù)組的右邊界和左邊界；

尋找右邊界：

從前往后遍歷的過(guò)程中，用 max 記錄遍歷過(guò)的最大值，如果 max 大于當(dāng)前的 nums[i]，說(shuō)明nums[i] 的位置不正確，屬于需要排序的數(shù)組，因此將右邊界更新為 i，然后更新 max；這樣最終可以找到需要排序的數(shù)組的右邊界，右邊界之后的元素都大于 max；

尋找左邊界：

從后往前遍歷的過(guò)程中，用 min 記錄遍歷過(guò)的最小值，如果 min 小于當(dāng)前的 nums[j]，說(shuō)明 nums[j] 的位置不正確，應(yīng)該屬于需要排序的數(shù)組，因此將左邊界更新為j，然后更新 min；這樣最終可以找到需要排序的數(shù)組的左邊界，左邊界之前的元素都小于 min；

注：從前往后遍歷和從后往前遍歷兩個(gè)過(guò)程可以分兩次循環(huán)完成，也可以放一起完成，這樣的話就有：j = len-i-1

public static int findUnsortedSubarray(int[] nums) {int len = nums.length;int max = nums[0]; // max記錄遍歷過(guò)的最大值int min = nums[len - 1]; // min記錄遍歷過(guò)的最小值int left = 0, right = -1; // 要排序數(shù)組的左邊界、右邊界for (int i = 0; i < len; i++) {// 從前往后遍歷if (max > nums[i]) {right = i;} else {max = nums[i];}// 從后往前遍歷if (min < nums[len - i - 1]) {left = len - i - 1;} else {min = nums[len - i - 1];}}return right - left + 1; }

方法 3 執(zhí)行用時(shí)：

總結(jié)

以上是生活随笔為你收集整理的leetcode 581. 最短无序连续子数组（详解普通 / 进阶 / 单调栈解法，Java版）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。