應該是昨天的
1574. Shortest Subarray to be Removed to Make Array Sorted
給一個矩陣arr 長度為n
從arr中移出一個subarray使arr中的元素為non-decreasing
請回傳subarray的最短長度
思路 :
這題我不太會講
假設刪掉subarray後的矩陣為arr*
這題就找出最長的arr*
因為只能移除一個subarray
所以arr*的開頭或結尾元素至少有一個跟arr一樣
假設arr[0]~arr[L]是non-decreasing
arr[R]~arr[n]是non-decreasing
令ans=min(n-L-1,R)
接著令i=0 , j=R
如果arr[i]<=arr[j]
i++ 且 ans=min(ans,j-i-1)
反之就
j