leetcode581. 最短無序連續子數組
給定一個整數數組，你需要尋找一個
連續的子數組，如果對這個子數組進行升序排序，那麼整個數組都會變為升序排序。
你找到的子數組應是
最短的，請輸出它的長度。
示例 1:輸入: [2, 6, 4, 8, 10, 9, 15]
輸出: 5
解釋: 你隻需要對 [6, 4, 8, 10, 9] 進行升序排序，那麼整個表都會變為升序排序。
- 輸入的數組長度範圍在 [1, 10,000]。
- 輸入的數組可能包含 重複 元素 ，是以 升序 的意思是 <=。
方法一：排序+雙指針
思路：
這道題的首先想到的方法比較暴力，既然要找到最短需要排序的數組，那麼我們就将數組排序，然後使用左右兩個指針，找到左邊第一個與原來元素不一樣的位置和右邊第一個與原來元素不一樣的位置，這兩個指針中間的數組就是答案，傳回長度即可。
需要注意的是，如果左右指針周遊過後，j<=i，那麼說明原數組就是有序的，傳回0；j=i是特殊情況，此時數組隻有一個元素，顯然是有序的。
複雜度分析：
- 使用python的sort函數，需要nlogn，之後雙指針最差情況是2n，是以綜合起來 時間複雜度為O(NlogN)
- 使用了一個額外的數組來存放原來的數組， 是以空間複雜度為 O(N)
代碼：
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
#存放原數組
temp = []
temp[:] = nums[:]
#排序
nums.sort()
n = len(nums)
#左指針，找到第一個不比對的下标
i = 0
while i < n:
if nums[i] == temp[i]:
i += 1
else:
break
j = n-1
#右指針，找到右邊第一個不比對的下标
while j >= 0:
if nums[j] == temp[j]:
j -= 1
else:
break
#傳回答案，如果j<=i，說明原來的數組就是有序數組
return j-i+1 if j-i>0 else 0
結果：
方法二：單調棧
思路：
這種方法與上面類似，都是找到最後
左邊第一個不比對以及右邊第一個不比對，隻不過我們不是使用排序之後對比，
我們使用單調棧來找到這兩個位置，也就是無序數組的左右下标。首先找到左下标，從左邊周遊數組，将它的下标入棧。周遊的時候，比較這個元素與棧頂下标對應的元素大小，如果大于等于它，證明目前還是升序的，不是無序的，就入棧......
如果小于棧頂坐标對應的元素，那麼證明這個元素的位置肯定不對，我們需要找到它的位置，将棧頂出棧，目前周遊的元素起碼需要與它換位，繼續與棧頂對應的元素比較......
直到棧頂對應的元素小于目前周遊的元素，那麼這個元素
需要變換到的位置就是上一個出棧元素的位置，使用left儲存。再将這個元素入棧。不斷周遊重複這個過程，left保留最小的需要變換位置...
那麼最後的left就是無序數組的左下标（即需要換位的最小元素需要換到的位置）。
同理，我們再從右周遊數組，維護一個遞減棧，
找到需要換位的最大元素需要換到的位置，也就是無序數組的右下标right。最後與上種方法一樣，如果right>left，傳回right-left+1，否則傳回0。
複雜度分析：
- 因為沒有進行排序，隻是周遊了兩次數組，是以 時間複雜度為O(2N)→O(N)
- 使用了一個棧，最長為N， 空間複雜度為O(N)
代碼：
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
stack = []
n = len(nums)
left = n-1
right = 0
#從左邊周遊，找到無序數組的左下标
for i in range(n):
while stack and nums[i] < nums[stack[-1]]:
temp = stack.pop()
left = min(left,temp)
stack.append(i)
stack = []
#從右邊周遊，找到無序數組的右下标
for i in range(n-1,-1,-1):
while stack and nums[i] > nums[stack[-1]]:
temp = stack.pop()
right = max(right,temp)
stack.append(i)
return right-left+1 if right>left else 0
結果：
