---

1574. 删除最短的子数组使剩余数组有序

• 标签：数组、双指针、二分查找
• 难度：中等

题目链接

• 1574. 删除最短的子数组使剩余数组有序 - 力扣

题目大意

描述：给定一个整数数组 $arr$。可以删除一个非空子数组（可以是连续的一段）。

要求：返回使剩余元素构成非递减序列所需删除的最短子数组长度。

说明：

• $1 \le arr.length \le 10^5$。
• $0 \le arr[i] \le 10^9$。

示例：

• 示例 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]。

解题思路

思路 1：双指针

1. 核心思想

最终的有序数组由三部分组成：左侧有序前缀 + 中间删除部分 + 右侧有序后缀。

如果我们删除中间一段，剩余的是左侧的某个前缀和右侧的某个后缀的拼接。要使得拼接后有序，需要 $arr[l] \le arr[r]$（左侧最后一个元素 $\le$ 右侧第一个元素）。

先找出最长的有序前缀和有序后缀。然后尝试组合。

2. 具体步骤

第 1 步：找最长的有序前缀：从左到右找到第一个 $arr[i] > arr[i+1]$ 的位置 $l$。$[0, l]$ 是有序的。

第 2 步：找最长的有序后缀：从右到左找到第一个 $arr[j] < arr[j-1]$ 的位置 $r$。$[r, n-1]$ 是有序的。

第 3 步：如果整个数组已经有序（$l == n-1$），返回 $0$。

第 4 步：初始答案为 $min(n - l - 1, r)$（只保留前缀或只保留后缀）。

第 5 步：双指针合并：

• $i = 0$，$j = r$。
• 当 $i \le l$ 且 $j < n$：
  • 如果 $arr[i] \le arr[j]$：可以拼接，$ans = min(ans, j - i - 1)$，$i++$。
  • 否则：$j++$（后缀的起始太小，需要右移）。

第 6 步：返回 $ans$。

3. 举例说明

以 $arr = [1,2,3,10,4,2,3,5]$ 为例：

有序前缀：$[1,2,3,10]$，$l=3$。
有序后缀：$[2,3,5]$，$r=4$。

初始答案 $= min(7-3-1=3, 4) = 3$。

双指针：

• $i=0$ ($1$)，$j=4$ ($2$)：$1 \le 2$，拼接长度 $4-0-1=3$，$ans=3$。$i=1$。
• $i=1$ ($2$)，$j=4$ ($2$)：$2 \le 2$，拼接长度 $4-1-1=2$，$ans=2$。$i=2$。
• $i=2$ ($3$)，$j=4$ ($2$)：$3 > 2$，$j=5$。
• $i=2$ ($3$)，$j=5$ ($3$)：$3 \le 3$，拼接长度 $5-2-1=2$，$ans=2$。$i=3$。
• $i=3$ ($10$)，$j=5$ ($3$)：$10 > 3$，$j=6$。
• $i=3$ ($10$)，$j=6$ ($5$)：$10 > 5$，$j=7$。
• $i=3$ ($10$)，$j=7$ 超出。

结果 $2$，删除 $[10,4]$。

验证：$[1,2,3,2,3,5]$ 有序。✓

思路 1：代码

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        # 找到有序前缀右边界
        l = 0
        while l + 1 < n and arr[l] <= arr[l + 1]:
            l += 1
        if l == n - 1:  # 整个数组已有序
            return 0

        # 找到有序后缀左边界
        r = n - 1
        while r > 0 and arr[r - 1] <= arr[r]:
            r -= 1

        # 初始答案：只保留前缀或只保留后缀
        ans = min(n - l - 1, r)

        # 双指针合并
        i, j = 0, r
        while i <= l and j < n:
            if arr[i] <= arr[j]:
                ans = min(ans, j - i - 1)
                i += 1
            else:
                j += 1

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n)$，一次遍历。
• 空间复杂度：$O(1)$。