难度: Medium
给你一个整数数组 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^50 <= arr[i] <= 10^9运行时间: 41 ms
内存: 29.1 MB
class Solution:
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
n = len(arr)
r = n - 1
while r > 0 and arr[r-1] <= arr[r]:
r-=1
if r == 0:
return 0
ans = r
l = 0
while l == 0 or arr[l - 1] <= arr[l]:
while r < n and arr[r] < arr[l]:
r += 1
ans = min(ans,r-l-1)
l += 1
return ans
这个题解首先从数组的右侧开始查找，寻找第一个破坏非递减规则的位置，即找到第一个arr[r-1] > arr[r]的位置。如果整个数组已经是非递减的（即r为0），则直接返回0，因为不需要删除任何元素。随后，题解尝试从数组左边开始，尝试与右侧的元素匹配以形成最大的非递减序列。对于每个左侧的元素arr[l]，通过增加r来跳过所有小于arr[l]的元素，直到arr[r] >= arr[l]。这样可以确定一个删除区间[l+1, r-1]。题解过程中始终维护这个区间的最小长度。这种方法有效地将问题划分为找到可以保留的左侧和右侧的最长非递减序列，然后计算两者之间需要删除的最短区间长度。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
n = len(arr)
r = n - 1
# 从右向左找到第一个破坏升序的位置
while r > 0 and arr[r-1] <= arr[r]:
r -= 1
# 整个数组已经是升序的
if r == 0:
return 0
ans = r # 初始化需要删除的最少元素数量
l = 0
# 从左向右尝试，尝试找到尽可能小的删除区间
while l == 0 or arr[l - 1] <= arr[l]:
# 调整r，直到arr[r]不小于arr[l]
while r < n and arr[r] < arr[l]:
r += 1
# 更新最小删除区间长度
ans = min(ans, r - l - 1)
l += 1
return ans
在这个题解中，使用 arr[r-1] > arr[r] 是为了找到确切的位置，其中元素的顺序从非递减突然变为递减，表明需要从此处开始调整。如果使用 arr[r-1] >= arr[r]，则也会包括相等的元素，这本身并不破坏非递减的顺序，因此不需要被考虑在内。题解的目标是尽可能减少需要删除的元素数量，只有在真正存在顺序递减的情况下才考虑删除。
是的，这个逻辑能够处理所有输入数组已经是非递减的情况。当从数组的最右端开始向左检查，并且没有找到任何违反非递减规则的元素时（即没有找到使得 arr[r-1] > arr[r] 的 r），r 会减减到 0。这意味着整个数组从左到右都是非递减的，因此不需要删除任何元素，直接返回 0 是正确的处理方式。
题解通过确保每次增加 r 时，都检查 arr[r] 是否小于 arr[l]。这个过程保证只有当 arr[r] 小于 arr[l] 时才增加 r，确保没有错过任何可能的 arr[r] >= arr[l] 的情况，从而不会错过可能的最小删除区间。一旦 arr[r] 大于等于 arr[l]，算法会计算并可能更新最小删除区间的长度，因此可以确保找到真正的最小删除区间。
在算法中，r 和 l 的值始终被保持在合法的索引范围内。l 从 0 开始，并在每次循环中增加，但不会超过 r-1，因此 l 始终小于 n。r 从 n-1 开始，只有当 arr[r] < arr[l] 时才会增加，但增加的前提是 r < n，确保 r 的值不会超过数组长度。因此，使用 r 和 l 计算最小删除区间长度时，它们都是合法的索引，不会引起越界问题。