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

只能删掉连续的一段，这道题要你删哪里

给你一个数组 arr，只能删掉其中连续一段子数组，把左右剩下的接起来、要求整体非递减（后一个不小于前一个，相等允许）。返回这段的最短长度，删空段也算，本就有序时答案 0。题面 arr=[1,2,3,10,4,2,3,5] 的答案是 3。

为什么不去枚举每一种能删的区间

枚举被删区间的左右端点约 n² 对，每挖一段还要扫一遍验剩下是否非递减、又一趟 O(n)，合起来 n³ 量级。数组长到 10⁵ 跑不完，得找扫一两遍就定答案的办法。

删完剩下的，为什么一定是前缀接后缀

只能删一段连续区间，挖掉后左边留开头一段前缀、右边留结尾一段后缀，中间空了。形状锁死成前缀接后缀，就不必枚举所有删法，只要分别求最长非递减前缀和后缀、在接缝处对接。对接用双指针：两个下标各从一端往里挪，一个盯前缀留到哪、一个盯后缀从哪接。

前后缀怎么框出来，两个指针又各往哪挪

从左扫最长非递减前缀、末尾记成 i：arr[k] ≤ arr[k+1] 就延伸，一断就停。再从右扫最长非递减后缀、起点记成 j。若 i 已不小于 j，整条本就非递减，直接返回 0。

否则先备两个保底：只留前缀删 n−i−1、只留后缀删 j，取较小的。再上双指针，l 从前缀头、r 从后缀头出发。arr[l] ≤ arr[r] 时接缝能拼，删中间 r−l−1 个、右移 l 多留一格前缀；接不上就右移 r 丢掉太小的后缀头。两指针都只右走，取全程最短删法。

拿 arr = 1,2,3,10,4,2,3,5 走一遍

从左扫前缀，1≤2≤3≤10 都成立，到 10 比后面的 4 大就断，前缀 1,2,3,10、末尾下标 3。从右扫后缀，5 起步、3≤5、2≤3 成立，到 4 比后面的 2 大就断，后缀 2,3,5、起点下标 5。两个保底：只留前缀删 8−3−1=4、只留后缀删 5，取小得 4。

再走双指针。l=0（值 1）配 r=5（值 2）能拼、删 4 个；l 右移到 1（值 2）配 r=5（值 2）仍能拼，删 3,10,4 三个、答案降到 3。l 到 2（值 3）比 r 的 2 大接不上，r 右移到 6（值 3）又能拼、还是删 3 个。l 到 3（值 10）比后缀的 3、5 都大、接不上，r 走出界结束。最短删 3 个：留 1,2 接 2,3,5，拼成 1,2,2,3,5，非递减。

前后缀用严格小于去扩，相等的那一截就被冤枉删掉

时间上 l 和 r 各自只右走、合起来最多 2n 步，加前后缀两遍扫描，整体 O(n)；空间只几个下标变量，O(1)。页面参考代码是等价写法，对前缀里每个 l 在后缀区间做二分、找第一个不小于 arr[l] 的位置，答案与双指针一致。它每处一趟二分、O(n log n)，比双指针慢一档。

还有几个地方要核。前后缀延伸要用「不大于」（arr[k] ≤ arr[k+1]）、别写成严格小于，相等本就合法，像 1,2,2 用小于号会在两个 2 之间断开、把相等段也算进删除。i 是否已不小于 j 要先判、成立就返回 0，否则会对有序数组做无谓归并。别忘保底 min(n−i−1, j)，像 5,4,3,2,1 双指针接不上，全靠它给 4。

Python

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

C++

#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;
    }
};

Java

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;
    }
}