Skip to content

Latest commit

 

History

History
178 lines (123 loc) · 6.14 KB

1574.shortest-subarray-to-be-removed-to-make-array-sorted.md

File metadata and controls

178 lines (123 loc) · 6.14 KB

题目地址(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)$

相关题目

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。