应该是昨天的
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