第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
1574. 删除最短的子数组使剩余数组有序
题目地址（1574. 删除最短的子数组使剩余数组有序）
题目描述
1
给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。
2
3
一个子数组指的是原数组中连续的一个子序列。
4
5
请你返回满足题目要求的最短子数组的长度。
6
7
8
9
示例 1：
10
11
输入：arr = [1,2,3,10,4,2,3,5]
12
输出：3
13
解释：我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。
14
另一个正确的解为删除子数组 [3,10,4] 。
15
示例 2：
16
17
输入：arr = [5,4,3,2,1]
18
输出：4
19
解释：由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。
20
示例 3：
21
22
输入：arr = [1,2,3]
23
输出：0
24
解释：数组已经是非递减的了，我们不需要删除任何元素。
25
示例 4：
26
27
输入：arr = [1]
28
输出：0
29
30
31
提示：
32
33
1 <= arr.length <= 10^5
34
0 <= arr[i] <= 10^9
Copied!
前置知识
- 双指针
公司
- 暂无
思路
首先考虑如果题目不要求必须删除连续的子数组，而是任意的子序列。那么我们可以使用 LIS（最长上升子序列模型）求出 LIS 长度，然后用 n 减去它即可。对于 LIS 模型不熟悉的，可以看下我的这篇文章。
这道题是求极值的，我首先想到的 DP，简单思考了下没啥思路。 而这道题要求我们必须连续，那就考虑滑动窗口。
首先我们将数组分成三部分 A，B，C（A，B，C 都可为空）。由于删除必须连续，因此我们不能只删除 A，C，除此之外可以随便删除。这是题目条件，也是解决问题的关键之一。
不难看出题目的解空间上界是 n - 1，下界是 0，其中 n 为数组长度。
进一步思考。题目的上界其实也可以是
n - 最长连续非递减子序列的长度。我们可以扫描一次数组，统计最长的连续非递减的子序列长度即可。Java 代码：
1
ans = cnt = 1
2
for(int i = 1; i < A.length; i++ ) {
3
if (A[i] >= A[i - 1]) {
4
cnt++
5
}
6
else {
7
ans = max(ans, cnt)
8
cnt = 1
9
}
10
}
Copied!
这样 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:
1
class Solution:
2
def findLengthOfShortestSubarray(self, A: List[int]) -> int:
3
n = len(A)
4
l, r = 0, n - 1
5
6
while l < n - 1 and A[l] <= A[l + 1]:
7
l += 1
8
if l == n - 1:
9
return 0
10
while r > 0 and A[r] >= A[r - 1]:
11
r -= 1
12
ans = min(r, n - l - 1)
13
i = 0
14
while i <= l and r < n:
15
if A[i] <= A[r]:
16
# delete i + 1 ~ r - 1
17
ans = min(ans, r - i - 1)
18
i += 1
19
else:
20
# extend the sliding window
21
r += 1
22
return ans
Copied!
C++ Code:
1
class Solution {
2
public:
3
int findLengthOfShortestSubarray(vector<int>& A) {
4
int N = A.size(), left = 0, right = N - 1;
5
while (left + 1 < N && A[left] <= A[left + 1]) ++left;
6
if (left == A.size() - 1) return 0;
7
while (right > left && A[right - 1] <= A[right]) --right;
8
int ans = min(N - left - 1, right), i = 0, j = right;
9
while (i <= left && j < N) {
10
if (A[j] >= A[i]) {
11
ans = min(ans, j - i - 1);
12
++i;
13
} else ++j;
14
}
15
return ans;
16
}
17
};
Copied!
复杂度分析
- 时间复杂度：$O(N)$，其中 N 为数组长度。
- 空间复杂度：$O(1)$
相关题目
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago