# 1574. 删除最短的子数组使剩余数组有序
### 题目地址（1574. 删除最短的子数组使剩余数组有序）
### 题目描述
```
给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。
一个子数组指的是原数组中连续的一个子序列。
请你返回满足题目要求的最短子数组的长度。
示例 1：
输入：arr = [1,2,3,10,4,2,3,5]
输出：3
解释：我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。
另一个正确的解为删除子数组 [3,10,4] 。
示例 2：
输入：arr = [5,4,3,2,1]
输出：4
解释：由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。
示例 3：
输入：arr = [1,2,3]
输出：0
解释：数组已经是非递减的了，我们不需要删除任何元素。
示例 4：
输入：arr = [1]
输出：0
提示：
1 <= arr.length <= 10^5
0 <= arr[i] <= 10^9
```
### 前置知识
* 双指针
* [滑动窗口](/leetcode-solution/thinkings/slide-window.md)
### 公司
* 暂无
### 思路
首先考虑如果题目不要求必须删除连续的子数组，而是任意的子序列。那么我们可以使用 LIS（最长上升子序列模型）求出 LIS 长度，然后用 n 减去它即可。对于 LIS 模型不熟悉的，可以看下我的[这篇文章](https://lucifer.ren/blog/2020/06/20/LIS/)。
这道题是求极值的，我首先想到的 DP，简单思考了下没啥思路。 而这道题要求我们必须连续，那就考虑滑动窗口。
首先我们将数组分成三部分 A，B，C（A，B，C 都可为空）。由于删除必须连续，因此我们不能只删除 A，C，除此之外可以随便删除。这是题目条件，也是解决问题的关键之一。
不难看出题目的解空间上界是 n - 1，下界是 0，其中 n 为数组长度。
进一步思考。题目的上界其实也可以是 `n - 最长连续非递减子序列`的长度。我们可以扫描一次数组，统计最长的连续非递减的子序列长度即可。
Java 代码：
```java
ans = cnt = 1
for(int i = 1; i < A.length; i++ ) {
if (A[i] >= A[i - 1]) {
cnt++
}
else {
ans = max(ans, cnt)
cnt = 1
}
}
```
这样 ans 就是 **最长连续非递减子序列** 的长度了。
但是显然这只是上界， 并不是正确解。一个显而易见的反例是：
如图我们取蓝色部分，而将红色部分删除，答案可能会更小。
实际上，这道题的思路和[11. 盛最多水的容器](/leetcode-solution/medium/11.container-with-most-water.md) 有点类似。只是这道题比较隐蔽，不那么容易想到。因此大家可以先从那道题开始，了解下这个套路。
一个可行的思路是初始化两个指针，一个指向头部，一个指向从尾部起第一个拐点（如上图右边蓝色部分的左端点）。
假设左指针为 i 右指针为 j，我们只需要不断右移左指针，左移右指针，并根据 i 和 j 的相对大小更新窗口即可。
值得注意的是，左指针不应该超过右侧第一个拐点，右指针也不应该超过左侧第一个拐点，原因就是前面讲到的**不能只删除 A，C**。 因此左指针移动的过程是单调非递减的，右指针是单调非递增的。这是本题的重中之重。
具体来说：
* 如果 A\[i] <= A\[j]，我们可以选择删除 \[i+1,j-1] 得到一个**候选解**。
* 如果 A\[i] > A\[j]，屋面不仅无法通过删除 \[i+1,j-1] 得到候选解，并且大于 A\[i] 的更不用看了，更加不会满足。又由于上面分析的 A\[i] 移动过程是单调不递减的，因此就没有必要继续移动了。我们可以通过右移左指针来排序所有的 \[i+1, j-1]，\[i+2, j- 1]，.....。
当然这里面还有一些细节，大家需要看代码才能完整领会。强烈建议大家自己写画一个图，然后写一遍，特别需要注意各种边界的判断。
### 关键点
* 画图
* 边界条件的考察（比如+1 -1 等号）
### 代码
代码支持：C++，Python3
Python3 Code:
```python
class Solution:
def findLengthOfShortestSubarray(self, A: List[int]) -> int:
n = len(A)
l, r = 0, n - 1
while l < n - 1 and A[l] <= A[l + 1]:
l += 1
if l == n - 1:
return 0
while r > 0 and A[r] >= A[r - 1]:
r -= 1
ans = min(r, n - l - 1)
i = 0
while i <= l and r < n:
if A[i] <= A[r]:
# delete i + 1 ~ r - 1
ans = min(ans, r - i - 1)
i += 1
else:
# extend the sliding window
r += 1
return ans
```
C++ Code:
```cpp
class Solution {
public:
int findLengthOfShortestSubarray(vector& A) {
int N = A.size(), left = 0, right = N - 1;
while (left + 1 < N && A[left] <= A[left + 1]) ++left;
if (left == A.size() - 1) return 0;
while (right > left && A[right - 1] <= A[right]) --right;
int ans = min(N - left - 1, right), i = 0, j = right;
while (i <= left && j < N) {
if (A[j] >= A[i]) {
ans = min(ans, j - i - 1);
++i;
} else ++j;
}
return ans;
}
};
```
**复杂度分析**
* 时间复杂度：$O(N)$，其中 N 为数组长度。
* 空间复杂度：$O(1)$
### 相关题目
* [11. 盛最多水的容器](/leetcode-solution/medium/11.container-with-most-water.md)
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1574.shortest-subarray-to-be-removed-to-make-array-sorted.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.