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

题目链接：1574. 删除最短的子数组使剩余数组有序

给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。

一个子数组指的是原数组中连续的一个子序列。

请你返回满足题目要求的最短子数组的长度。

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

示例 3：

输入：arr = [1,2,3]
输出：0
解释：数组已经是非递减的了，我们不需要删除任何元素。

示例 4：

输入：arr = [1]
输出：0

提示：

• 1 <= arr.length <= 10^5
• 0 <= arr[i] <= 10^9

思路

题目要求删除的是子数组，子数组是连续的，我们可以采用枚举这个数组的两端。因为最终整体是单调的，也就是左端点的左边和右端点的右边是单调的。那么当左边端点往右移动时，右边端点不可能往左移动（假设左端点i，右端点j的时候，arr[:i] + arr[j+1:]满足单调，那么arr[i-1] <= arr[j+1]，而左端点右移后新的左端点i'满足arr[i - 1] <= arr[i' - 1]），所以可以使用双指针。

方法

双指针，枚举左端点对应的右端点，看最小的是哪个。注意当左端点出现拐点时，说明这里必须删除，没有必要继续右移了。

Python代码

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        j = n - 1
        while j and arr[j]>= arr[j-1]:
            j -= 1
        if not j:
            return 0
        ans = j
        for i in range(0, n-1):
            while j < n and arr[j] < arr[i]:
                j += 1
            ans = min(ans, j - i - 1)
            if arr[i + 1] < arr[i]:
                break
        return ans