Links

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)$

相关题目

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。