1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
# 1574. Shortest Subarray to be Removed to Make Array Sorted
"""
given an integer array 'arr', remove a subarray (can be empty) from 'arr'
such that the remaining elements in 'arr' are non-decreasing. return the
length of the shortest subarray to remove. a subarray is a contiguous
subsequence of the array.
"""
class Solution(object):
def findLengthOfShortestSubarray(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
left, right = 0, len(arr) - 1
while left < right and arr[left + 1] >= arr[left]:
left += 1
if left == len(arr) - 1:
return 0
while right > 0 and arr[right - 1] <= arr[right]:
right -= 1
ans = min(len(arr) - left - 1, right)
for i in range(left + 1):
if arr[i] <= arr[right]:
ans = min(ans, right - i - 1)
elif right < len(arr) - 1:
right += 1
else:
break
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.findLengthOfShortestSubarray(arr=[1, 2, 3, 10, 4, 2, 3, 5]))
print(obj.findLengthOfShortestSubarray(arr=[5, 4, 3, 2, 1]))
print(obj.findLengthOfShortestSubarray(arr=[1, 2, 3]))
|