题目描述

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

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

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

样例

输入：arr = [1,2,3,10,4,2,3,5]
输出：3
解释：我们需要删除的最短子数组是 [10,4,2]，长度为 3。
剩余元素形成非递减数组 [1,2,3,3,5]。
另一个正确的解为删除子数组 [3,10,4]。

输入：arr = [5,4,3,2,1]
输出：4
解释：由于数组是严格递减的，我们只能保留一个元素。
所以我们需要删除长度为 4 的子数组，要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。

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

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

限制

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

算法

(贪心) $O(n)$

1. 最终答案一定是 前缀 + 后缀 的形式，前缀和后缀必须单调非递减，但前缀或后缀可以为空。
2. 对于前缀的每个位置 $i$，找到最小的后缀起始位置 $j > i$，满足 $arr[i] \le arr[j]$，然后更新答案。
3. 注意到 $j$ 是随着 $i$ 的增大而不减的。

时间复杂度

• 每个位置最多遍历两次，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

Go 代码

func findLengthOfShortestSubarray(arr []int) int {
    n := len(arr)

    j := n-1
    for j > 0 && arr[j-1] <= arr[j] {
        j--
    }

    ans := n-j
    for i := 0; i < n; i++ {
        if i > 0 && arr[i] < arr[i-1] {
            break
        }
        for j <= i || (j < n && arr[i] > arr[j]) {
            j++
        }

        if ans < i+1+n-j {
            ans = i+1+n-j
        }
    }

    return n-ans
}