数组（四）-- LC[1574] 删除最短的子数组使剩余数组有序

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

1.1 题目描述

        题目链接：https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/description/

1.2 滑动窗口

1. 枚举左端点，移动右端点

        核心思路：枚举 $\text{left}$，增大 $\text{right}$ 直到 $\text{arr}[\text{left}]\le \text{arr}[\text{right}]$，此时更新子数组长度的最小值。

解疑答惑：

        问：为什么枚举一个新的 $\text{left}$ 时，$\text{right}$ 不会往左移？或者说，是否需要再次枚举之前枚举过的 $\text{arr}[\text{right}]$？

        答：在向右移动时，由于 $\text{arr}[\text{left}]$ 和 $\text{arr}[\text{right}]$ 都是非递减的，所以 $\text{right}$ 左侧之前枚举过的元素必然小于 $\text{arr}[\text{left}]$，无需再次枚举。这也是本题可以使用同向双指针（不定长滑动窗口）的前提。

        问：在计算子数组长度时，我经常分不清下标是否要 +1 或 −1，请问如何解决？

        答：第一，时刻把握住 $\text{left}$ 和 $\text{right}$ 的含义，对于本题来说是开区间 $(\text{left},\text{right})$，这两个指针指向的元素不能删除。第二，可以代入一些数据来验证，比如代入 $\text{left}=1,\text{right}=3$，此时只需要删除一个 $\text{arr}[2]$，所以公式 $\text{right}-\text{left}-1$ 才是符合要求的。

        问：为什么不用判断$\text{left}<\text{right}$，难道不会出现 $\text{left}\ge \text{right}$ 的情况吗？

        答：由于提前判断了 $\text{arr}$ 是非递减数组的情况，后面的循环 $\text{left}$ 必定小于 $\text{right}$。反证：如果某个时刻 $\text{left}$ 达到了 $\text{right}$，就说明整个数组是有序的，但这种情况已经提前判断了。

        问：能不能先把 $\text{left}$ 的最大值算出来，然后再去枚举 $\text{left}$ 或 $\text{right}$？

        答：可以。根据对称性，这种做法和先算 $\text{right}$ 的最小值的做法是一样的，只不过枚举的顺序相反而已。

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        right = n - 1
        while right and arr[right - 1] <= arr[right]:
            right -= 1
        if right == 0:  # arr 已经是非递减数组
            return 0
        # 此时 arr[right-1] > arr[right]
        ans = right  # 删除 arr[:right]
        left = 0  # 枚举 left
        while left == 0 or arr[left - 1] <= arr[left]:
            while right < n and arr[right] < arr[left]:
                right += 1
            # 此时 arr[left] <= arr[right]，删除 arr[left+1:right]
            ans = min(ans, right - left - 1)
            left += 1
        return ans

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $\text{nums}$ 的长度。虽然写了个二重循环，但是内层循环中对 $\text{right}$ 加一的总执行次数不会超过 $n$ 次，所以总的时间复杂度为 $O(n)$。
• 空间复杂度：$O(1)$，仅用到若干额外变量。

2. 枚举右端点，移动左端点

        核心思路：枚举 $\text{right}$，增大 $\text{left}$ 直到 $\text{arr}[\text{left}]>\text{arr}[\text{right}]$。在增大过程中去更新子数组长度的最小值。

        问：为什么枚举一个新的 $\text{right}$ 时，$\text{left}$ 不会往左移？或者说，是否需要再次枚举之前枚举过的 $\text{arr}[\text{left}]$？

        答：在向右移动时，由于 $\text{arr}[\text{left}]$ 和 $\text{arr}[\text{right}]$ 都是非递减的，所以 $\text{left}$ 左侧之前枚举过的元素必然小于等于 $\text{arr}[\text{right}]$，由于这样的子数组长度更长，无需再次枚举。这也是本题可以使用同向双指针（不定长滑动窗口）的前提。

        问：为什么循环一定会结束？

        答：代码中提前判断了 $\text{arr}$ 已经是非递减数组的情况，所以后面的循环一定存在 $\text{left}$，使得 $\text{arr}[\text{left}]>\text{arr}[\text{left}+1]$ 成立。

注：最坏情况下，当 $\text{right}=n$ 时才会去移动 $\text{left}$。

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        right = n - 1
        while right and arr[right - 1] <= arr[right]:
            right -= 1
        if right == 0:  # arr 已经是非递减数组
            return 0
        # 此时 arr[right-1] > arr[right]
        ans = right  # 删除 arr[:right]
        left = 0
        while True:  # 枚举 right
            while right == n or arr[left] <= arr[right]:
                ans = min(ans, right - left - 1)  # 删除 arr[left+1:right]
                if arr[left] > arr[left + 1]:
                    return ans
                left += 1
            right += 1

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为 $\text{nums}$ 的长度。虽然写了个二重循环，但是内层循环中对 $\text{left}$ 加一的总执行次数不会超过 $n$ 次，所以总的时间复杂度为 $O(n)$。
• 空间复杂度：$O(1)$，仅用到若干额外变量。

---

参考

• 删除最短的子数组使剩余数组有序：https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/solutions/2189149/dong-hua-yi-xie-jiu-cuo-liang-chong-xie-iijwz/