題目內容
給定一個整數數組，你需要尋找一個連續的子數組，如果對這個子數組進行升序排序，那麼整個數組都會變為升序排序。
你找到的子數組應是最短的，請輸出它的長度。
示例 1：
輸入: [2, 6, 4, 8, 10, 9, 15] 輸出: 5 解釋: 你只需要對 [6, 4, 8, 10, 9] 進行升序排序，那麼整個表都會變為升序排序。說明：
輸入的數組長度範圍在 [1, 10,000]。輸入的數組可能包含重複元素 ，所以升序的意思是<=。來源：力扣（LeetCode）連結：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
解法效率
LeetCode的Python執行用時隨緣，只要時間複雜度沒有明顯差異，執行用時一般都在同一個量級，僅作參考意義。
解法一（暴力的棧實現）：
【思路】使用棧存儲當前遍歷的數組，如果發現新的數(n)比棧頂元素小，記錄棧頂的坐標作為排序數組的結束坐標(reverse_max_idx)；從棧中不斷取出元素，直到取出的元素比該數(n)大或達到棧底，此時的坐標即為排序數組的起始坐標(reverse_min_idx)；再將取出的元素升序放回棧中（可用另一個棧實現）。排序數組的起始坐標一旦被確定，就不再更改；而排序數組的結束坐標，則不斷更新。最終的結果即為排序樹組的結束坐標減去起始坐標。這種方法一直在維護一個升序的棧，但如果整個數組是一個倒序的數組，則會有巨大的時間複雜度。
def findUnsortedSubarray(self, nums: List[int]) -> int: stack = [] reverse_min_idx = None reverse_max_idx = None for i in range(len(nums)): n = nums[i] if len(stack) == 0 or n >= stack[-1]: stack.append(n) else: reverse_end_idx = i reverse_start_idx = i # 使用臨時棧到倒序部分升序 temp_stack = [] while len(stack) > 0 and n < stack[-1]: reverse_start_idx -= 1 temp_stack.append(stack.pop(-1)) temp_stack.append(n) while temp_stack: stack.append(temp_stack.pop(-1)) # 更新升序數組起始坐標和升序數組結尾坐標 if reverse_min_idx is None or reverse_start_idx < reverse_min_idx: reverse_min_idx = reverse_start_idx if reverse_max_idx is None or reverse_end_idx > reverse_max_idx: reverse_max_idx = reverse_end_idx if reverse_min_idx is not None and reverse_max_idx is not None: return reverse_max_idx - reverse_min_idx + 1 else: return 0解法二（暴力的維護最大值數組）：
【思路】解法一中，我們發現實際上我們需要維護完整的升序數組，只需要維護最大值數組即可。但是，這種方法和解法一擁有相似的時間複雜度，這種方法仍然無法解決倒序數組時間複雜度過大的問題。
def findUnsortedSubarray(self, nums: List[int]) -> int: max_list = [-1] * len(nums) reverse_min_idx = None reverse_max_idx = None for i in range(len(nums)): if (i > 0 and nums[i] >= max_list[i - 1]) or i == 0: max_list[i] = nums[i] else: # 維護最大值數組 max_list[i] = max_list[i - 1] # 計算起始坐標 idx = i - 1 while idx >= 0 and max_list[idx] > nums[i]: idx -= 1 idx += 1 # 更新升序數組起始坐標和升序數組結尾坐標 if reverse_min_idx is None or idx < reverse_min_idx: reverse_min_idx = idx if reverse_max_idx is None or i > reverse_max_idx: reverse_max_idx = i if reverse_min_idx is not None and reverse_max_idx is not None: return reverse_max_idx - reverse_min_idx + 1 else: return 0解法三（暴力的兩層循環）：
【思路】通過解法一和解法二我們發現，與其使用O(N^2)的時間複雜度來維護一個升序棧或一個最大值數組，還不如直接用O(N^2)的時間複雜度來比較數組中所有數之間的大小，僅維護需升序數組的起始坐標(reverse_min_idx)和結束坐標(reverse_max_idx)。我們比較數組中每兩個數組的大小，如果發現左邊的比右邊的大，那麼就判斷是否需要更新起始坐標(reverse_min_idx)和結束坐標(reverse_max_idx)。但是這種方法的時間複雜度仍然是O(N^2)。
def findUnsortedSubarray(self, nums: List[int]) -> int: reverse_min_idx = len(nums) - 1 reverse_max_idx = 0 for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] > nums[j]: reverse_min_idx = min(reverse_min_idx, i) reverse_max_idx = max(reverse_max_idx, j) if reverse_min_idx > reverse_max_idx: return 0 else: return reverse_max_idx - reverse_min_idx + 1解法四（排序）：
【思路】我們想到與其分別比較所有數組，還不如直接將數組排序；比較原數組和排序後數組不同之處的最小坐標和最大坐標，這些坐標也就是需要升序數組的起始坐標和結束坐標。這種方法的時間複雜度為排序的O(NlogN)和排序後遍歷的O(N)，時間複雜度大幅度下降。
def findUnsortedSubarray(self, nums: List[int]) -> int: minimum = len(nums) - 1 maximum = 0 sorts = sorted(nums) for i in range(len(nums)): if sorts[i] != nums[i]: minimum = min(minimum, i) maximum = max(maximum, i) return maximum - minimum + 1 if minimum < maximum else 0解法五（解法四的優化）：
【思路】我們再在解法四的基礎上做一個小小的優化，在遍歷時不再完整遍歷，而是從前往後、從後往前分別找到第一個存在差異的點即可。
def findUnsortedSubarray(self, nums: List[int]) -> int: sorts = sorted(nums) for i in range(len(nums)): if sorts[i] != nums[i]: minimum = i break else: return 0 for i in range(len(nums) - 1, -1, -1): if sorts[i] != nums[i]: maximum = i break else: return 0 return maximum - minimum + 1