1574. Shortest Subarray to be Removed to Make Array Sorted

题目信息

题号:

1574

难度:

Medium

主题:

数组、双指针、有序前后缀

原题:

LeetCode 1574

重点:

删除一个连续子数组后,剩余前缀与后缀拼接结果必须非递减;求最短删除长度

题目重述

给定整数数组 arr。可以删除一个连续子数组,删除后保留的前缀与后缀按原顺序直接拼接。

请返回使剩余数组按非递减顺序排列所需删除的最短长度。允许删除空子数组,也允许只保留一个元素。

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

自建示例

删除中间的单个峰值即可连接有序两侧:

输入:arr = [1,2,10,3,4]
输出:1
解释:删除 10 后得到 [1,2,3,4]。

严格递减数组最多只能保留一个元素:

输入:arr = [5,4,3]
输出:2
解释:删除任意两个元素后剩余单元素数组有序。