1574. 删除最短的子数组使剩余数组有序

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        # 先从两头找 打破非递减的 左右两点。
        l,r = 0,len(arr)-1
        if arr==[] or len(arr)==1: return 0
        while l+1<=len(arr)-1 and arr[l]<=arr[l+1]:
            l += 1
            if l==len(arr)-1: return 0      # 直接就是满足条件的。
        while r-1>=0 and arr[r]>=arr[r-1]:
            r -= 1
        # 选择 left 数组 加 right 数组的最长的非递减 组合。
        # 最开始 只有 right，逐步添加left看看合不合规。选最小的 删除长度。
        left,right = arr[:l+1],arr[r:]
        min_lenth = r 
        for i in range(l+1):
            j = bisect.bisect_left(right,left[i])
            min_lenth = min(min_lenth,r+j-i-1)
        return min_lenth