删除最短的子数组使剩余数组有序 图解题解

这道题到底在问什么

输入

arr=[1,2,3]

输出

0

输入

arr=[5,4,3,2,1]

输出

4

输入

arr=[1,2,3,10,4,2,3,5]

输出

3

先想最直接的笨办法

第五次比较。l 走到下标 3 值是 10,r 在下标 6 值是 3,10 比 3 大,接不上。前缀尾巴这个 10 太大了,后缀里得找个不小于 10 的数才能接。继续把 r 右移试试。（动画第 21 步）

最优解：一步一步想明白

1. 3记牢:剩下的一定是前缀加后缀。先求最长非递减前缀末尾 i、后缀起点 j;保底取 min(n-i-1, j);再双指针归并,arr[l] ≤ arr[r] 可拼、删 r-l-1 并 l 右移,接不上就 r 右移。
2. 4先看清画面。上面这排格子是 arr = 1,2,3,10,4,2,3,5,一共 8 个数。我们要删掉中间连续的一段,让剩下的从左到右非递减,并且删的这段越短越好。右边面板记三件事:非递减前缀到哪结束、非递减后缀从哪开始、目前找到的最短删除长度,现在都还没定。我们分两步先把前缀和后缀框出来。
3. 5先从左往右找最长的非递减前缀。第 0 个数 1 自己就是一段合法的非递减序列,标成绿色,绿色代表「保留下来的前缀」。接着我们一个个往右看,只要后一个不小于前一个,前缀就能继续延伸。
4. 6看下标 1 的 2,它和前一个 1 比,1 不大于 2,非递减没断,前缀往右长一格,现在是 1,2。绿色段也跟着多盖一格。继续往后看。
5. 7下标 2 的 3,和前一个 2 比,2 不大于 3,还在非递减,前缀延伸到 1,2,3。一路绿到下标 2。再看下一个。
6. 8下标 3 的 10,和前一个 3 比,3 不大于 10,非递减依然成立,前缀延伸到 1,2,3,10。这个 10 暂时被收进前缀,但它会不会成为麻烦,接着看。
7. 9到下标 4 的 4,和前一个 10 比,10 比 4 大,非递减在这里断了,标红提醒。所以最长非递减前缀就到下标 3 结束,记 i 等于 3,前缀是 1,2,3,10。前缀框定,接下来换个方向找后缀。
8. 10现在从右往左找最长的非递减后缀。最右边下标 7 的 5 自成一段,标成蓝色,蓝色代表「保留下来的后缀」。我们往左走,只要前一个不大于后一个,后缀就能往左延伸。
9. 11看下标 6 的 3,它的后一个是 5,3 不大于 5,非递减成立,后缀往左长到 3,5。蓝色段往左多盖一格。继续往左看。
10. 12下标 5 的 2,后一个是 3,2 不大于 3,还在非递减,后缀延伸到 2,3,5。蓝色盖到下标 5。再往左看一个。
11. 13到下标 4 的 4,它的后一个是 2,4 比 2 大,非递减断开,标红。所以最长非递减后缀从下标 5 开始,记 j 等于 5,后缀是 2,3,5。现在前缀末尾 i 是 3、后缀起点 j 是 5,i 小于 j,说明中间确实有东西要删。
12. 14动手归并之前,先准备两个保底答案。第一手:干脆只保留前缀 1,2,3,10,把后面 arr 下标 4 到 7 这一整段灰掉删掉,长度是 n 减 i 减 1,也就是 8 减 3 减 1 等于 4。这是一定可行的删法,先记下候选 4。
13. 15第二手:只保留后缀 2,3,5,把前面 arr 下标 0 到 4 灰掉删掉,长度就是 j 等于 5。这一手要删 5 个,比第一手差。两个保底取小,min(4,5) 等于 4,所以当前最短删除先定成 4。下面看双指针能不能把它压得更短。
14. 16关键一步来了。我们想保留更多两端、删更少中间。摆两个指针:l 从前缀的头部下标 0 出发,r 从后缀的头部下标 5 出发。思路是,保留前缀的 0 到 l 这一段,接上后缀的 r 到末尾这一段,只要接缝处不降,中间的 l 加 1 到 r 减 1 就是要删的部分,长度 r 减 l 减 1。开始归并。
15. 17第一次比较。l 在下标 0 值是 1,r 在下标 5 值是 2,1 不大于 2,接缝成立。保留前缀到下标 0,也就是 1,接上后缀 2,3,5,中间删 arr 下标 1 到 4,长度 r 减 l 减 1 等于 4。和保底一样,没变短。我们让 l 右移,尝试多保留一点前缀。
16. 18第二次比较。l 走到下标 1 值是 2,r 还在下标 5 值是 2,2 不大于 2,接缝成立。保留前缀 1,2,接上后缀 2,3,5,中间删 arr 下标 2 到 4,也就是 3,10,4,长度等于 3。比 4 更短,最短删除刷新成 3。l 继续右移。
17. 19第三次比较。l 在下标 2 值是 3,r 在下标 5 值是 2,这回 3 比 2 大,接缝降下来了,拼不上。问题出在后缀头那个 2 太小,没法接在 3 后面。办法是把 r 右移,等于把后缀头的 2 也删掉,换个更大的数来接。
18. 20第四次比较。r 右移到下标 6 值是 3,l 还在下标 2 值是 3,3 不大于 3,接缝成立,非递减允许相等。保留前缀 1,2,3,接上后缀 3,5,中间删 arr 下标 3 到 5,长度等于 3,和当前最短一样。l 再右移。
19. 21第五次比较。l 走到下标 3 值是 10,r 在下标 6 值是 3,10 比 3 大,接不上。前缀尾巴这个 10 太大了,后缀里得找个不小于 10 的数才能接。继续把 r 右移试试。
20. 22第六次比较。r 右移到下标 7 值是 5,l 还在下标 3 值是 10,10 比 5 大,还是接不上。后缀里再没有更大的数了,r 走到末尾外面,归并到此结束。那个 10 注定保不住,必须被删。
21. 23把归并里最短的那次删法摆出来。保留前缀 1,2,接上后缀 2,3,5,删掉中间灰色的 3,10,4 这三个数,剩下的 1,2,2,3,5 从左到右完全非递减。删 10,4,2 那一种也是删 3 个、剩 1,2,3,3,5,同样成立,两种都对、长度都是 3。
22. 24收个尾。整道题先用一次左右扫描框出最长非递减前缀和后缀,再用双指针归并在接缝处贪心地保留尽量多两端、删尽量少中间。arr = 1,2,3,10,4,2,3,5 最终最短删除长度是 3。两个指针都只往前走,线性时间、常数额外空间,既快又省。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        i, j = 0, n - 1
        while i + 1 < n and arr[i] <= arr[i + 1]:
            i += 1
        while j - 1 >= 0 and arr[j - 1] <= arr[j]:
            j -= 1
        if i >= j:
            return 0
        ans = min(n - i - 1, j)
        for l in range(i + 1):
            r = bisect_left(arr, arr[l], lo=j)
            ans = min(ans, r - l - 1)
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();
        int i = 0, j = n - 1;
        while (i + 1 < n && arr[i] <= arr[i + 1]) {
            ++i;
        }
        while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
            --j;
        }
        if (i >= j) {
            return 0;
        }
        int ans = min(n - 1 - i, j);
        for (int l = 0; l <= i; ++l) {
            int r = lower_bound(arr.begin() + j, arr.end(), arr[l]) - arr.begin();
            ans = min(ans, r - l - 1);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int i = 0, j = n - 1;
        while (i + 1 < n && arr[i] <= arr[i + 1]) {
            ++i;
        }
        while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
            --j;
        }
        if (i >= j) {
            return 0;
        }
        int ans = Math.min(n - i - 1, j);
        for (int l = 0; l <= i; ++l) {
            int r = search(arr, arr[l], j);
            ans = Math.min(ans, r - l - 1);
        }
        return ans;
    }

    private int search(int[] arr, int x, int left) {
        int right = arr.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

复杂度

面试官可能追问