1574. Shortest Subarray to be Removed to Make Array Sorted
## 思路
刪subarray有三種Case:
1. 去頭 -- arr[right:] 遞增
2. 去尾 -- arr[:left] 遞增
3. 刪中間 -- arr[:i] + arr[j:] 遞增
Two pointer
先找prefix, suffix遞增的array
再檢查Merge
## Code
```python
class Solution:
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
n = len(arr)
left, right = 0, n-1
while left < right and arr[left] <= arr[left+1]:
left += 1
while left < right and arr[right-1] <= arr[right]:
right -= 1
if left >= right:
return 0
res = min(n-left-1, right)
i, j = 0, right
while i <= left and j < n:
if arr[i] <= arr[j]:
res = min(res, j-i-1)
i += 1
else:
j += 1
return res
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.99 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1731684289.A.BBE.html