1574. 删除最短的子数组使剩余数组有序

题目地址（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 就是 最长连续非递减子序列 的长度了。

但是显然这只是上界，并不是正确解。一个显而易见的反例是：

如图我们取蓝色部分，而将红色部分删除，答案可能会更小。

实际上，这道题的思路和11. 盛最多水的容器有点类似。只是这道题比较隐蔽，不那么容易想到。因此大家可以先从那道题开始，了解下这个套路。

一个可行的思路是初始化两个指针，一个指向头部，一个指向从尾部起第一个拐点（如上图右边蓝色部分的左端点）。

假设左指针为 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)$

题目地址（1574. 删除最短的子数组使剩余数组有序）

题目描述

前置知识

公司

思路

关键点

代码

相关题目