1574. 删除最短的子数组使剩余数组有序
https://leetcode-cn.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted/description/
给你一个整数数组 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
- 双指针
- 暂无
首先考虑如果题目不要求必须删除连续的子数组，而是任意的子序列。那么我们可以使用 LIS（最长上升子序列模型）求出 LIS 长度，然后用 n 减去它即可。对于 LIS 模型不熟悉的，可以看下我的这篇文章。
这道题是 求极值的，我首先想到的 DP，简单思考了下没啥思路。 而这道题要求我们必须连续，那就考虑滑动窗口。
首先我们将数组分成三部分 A，B，C（A，B，C 都可为空）。由于删除必须连续，因此我们不能只删除 A，C，除此之外可以随便删除。这是题目条件，也是解决问题的关键之一。
不难看出题目的解空间上界是 n - 1，下界是 0，其中 n 为数组长度。
进一步思考。题目的上界其实也可以是
n - 最长连续非递减子序列的长度。我们可以扫描一次数组，统计最长的连续非递减的子序列长度即可。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 就是 最长连续非递减子序列 的长度了。
但是显然这只是上界， 并不是正确解。一个显而易见的反例是：
如图我们取蓝色部分，而将红色部分删除，答案可能会更小。
一个可行的思路是初始化两个指针，一个指向头部，一个指向从尾部起第一个拐点（如上图右边蓝色部分的左端点）。
假设左指针为 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:
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:
class Solution {
public:
int findLengthOfShortestSubarray(vector<int>& 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)$
更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 8mo ago