Leetcode 581. 最短无序连续子数组
题目描述
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
解法
以 left、right、maxIndex 分别作为待求子数组的左边界、右边界和最大值。由左向右遍历数组，并更新最大值下标。若当前元素小于最大值，则更新右边界 right 值，并由 left 向左遍历，直到元素不大于右边界 right 指向值。最终子数组长度为 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本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.05.30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读