題目描述
給定一個(gè)整數(shù)數(shù)組境蔼，你需要尋找一個(gè)連續(xù)的子數(shù)組暖夭，如果對(duì)這個(gè)子數(shù)組進(jìn)行升序排序步咪，那么整個(gè)數(shù)組都會(huì)變?yōu)樯蚺判颉?/p>
你找到的子數(shù)組應(yīng)是最短的，請(qǐng)輸出它的長(zhǎng)度蹦狂。
示例 1:
輸入: [2, 6, 4, 8, 10, 9, 15]
輸出: 5
解釋: 你只需要對(duì) [6, 4, 8, 10, 9] 進(jìn)行升序排序毫炉，那么整個(gè)表都會(huì)變?yōu)樯蚺判颉?/p>
解法
以 left圈浇、right切省、maxIndex 分別作為待求子數(shù)組的左邊界、右邊界和最大值蛔六。由左向右遍歷數(shù)組荆永，并更新最大值下標(biāo)。若當(dāng)前元素小于最大值国章，則更新右邊界 right 值具钥，并由 left 向左遍歷，直到元素不大于右邊界 right 指向值液兽。最終子數(shù)組長(zhǎng)度為 right - left + 1骂删。
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
left,right,maxIndex=None,0,0
for i in range(1,len(nums)):
if nums[i]>=nums[maxIndex]:
maxIndex=i
else:
right=i
if left==None:
left=i-1
while left>0 and nums[left-1]>nums[right]:
left-=1
return right-left+1 if left!=None else 0
