Readme

1574.Shortest-Subarray-to-be-Removed-to-Make-Array-Sorted

我们对于探索subarray的题目，归根结底就是确定它的两个边界。我们将整个数组可以分为三段[0,i],[i+1,j-1],[j,n-1]，中间的那段就是我们尝试删除的subarray。我们需要满足三个条件：[0:i]是单调增的，[j:n-1]是单调增的，并且arr[j]>=arr[i].

让我们尝试从头到尾遍历i可能的位置。条件1是比较容易判断的。一旦发现arr[i]<arr[i-1]的时候，条件1不能满足，注定就没有解了，整个搜索过程就可以终止了。

条件3也是容易实现的。就是从后往前遍历，可以找到最前的一个j使得满足[j:n-1]是单调的。

那么条件2怎么满足呢？如果此时arr[j]<arr[i]怎么办？显然因为[j:n-1]是单调增的，我们可以尝试往右移动j找到满足arr[j]>=arr[i]的第一个位置。此时我们就找到了一组{i,j}对应的是一个合法的拆分原数组的解（不见得是最优解）。

接下来我们遍历i的下一个位置。此时j怎么移动呢？我们发现，因为i的移动必须保证[0:i]单调增，所以arr[i]会变大，所以arr[j]必然也要增大以保证arr[j]>=arr[i]。我们还发现[j:n-1]也是单调增的区间，所以我们必然会将j右移。这样我们会找到下一个合适的j，使得此时的{i,j}成为一组合适的解。

同理的分析，我们每向右移动一次i指针，必然也必须向右移动j指针以寻找合适的{i,j}。这就是一个双指针的模式。所以我们用o(n)的时间复杂度就可以探索到所有合适的{i,j}.