给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。 一个子数组指的是原数组中连续的一个子序列。 请你返回满足题目要求的最短子数组的长度。 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：
题目要求我们寻找一个最短的子数组，使得删去它之后原数组变成非递减数组。那么我们可以考虑贪心策略。首先，我们需要找到最长的非递减子数组，这个子数组在最后的答案中肯定是不会被删除的，因为删去这个子数组回导致整个数组非递减性质被破坏。接着我们假设这个子数组的右端点为 i（当然我们还不知道实际的值是多少），那么我们接着考虑如何从左边找到最短的子数组，使得删去这个子数组之后原数组变为非递减数组。假设我们找到了左端点为 j 的子数组，那么这个子数组的长度就是 i-j-1。然后我们可以用一个变量 cnt 来统计需要从这个子数组中删去的数字的个数，这个变量的初始化值为 0，每当我们找到一个子数组的边界，而这个子数组又不是非递减的时候，我们就将这个子数组中从小到大排列的数字删掉并且让 cnt++。最终答案就是 i-j-1-cnt，即最长的非递减子数组长度减去从左边找到的最短需要删除的子数组的长度再减去被删除的数字个数。

具体实现可以使用单调栈，单调栈里存的是数组元素的下标，栈顶到栈底位置对应的元素值是单调不降的。遍历数组的时候，如果当前元素比单调栈的栈顶小，说明需要找到右端点，于是不断pop出深度直到栈顶元素小于当前元素或者栈空，此时当前元素的下标就是右端点。接着我们在单调栈里寻找左端点，这里需要注意我们需要从右往左遍历单调栈，因为要保证最先找到的左端点一定是在右端点左边的。用一个变量 cnt 统计需要删除的元素个数，最终计算答案得到结果。

时间复杂度：O(n)，两次单调栈遍历，最差情况下遍历整个数组。空间复杂度：O(n)，单调栈中的元素个数最大为 n。

代码：

相关问题

给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。 一个子数组指的是原数组中连续的一个子序列。 请你返回满足题目要求的最短子数组的长度。 C 语言

示例 1：

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

示例 2：

输入：arr = [5,4,3,2,1]
输出：1
解释：我们需要删除的最短子数组是 [5]，长度为 1。

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-subarray-to-be-removed-to-make-array-sorted
以下是C语言的解法：

给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。 一个子数组指的是原数组中连续的一个子序列。 请你返回满足题目要求的最短子数组的长度。代码

思路：双指针法

从左到右遍历数组，若出现 arr[i] > arr[i+1] ，则一定需要删除 arr[i]，但 arr[i] 是否需要删除还需进一步判断：

- 若存在 arr[i-1] > arr[i+1]，则 arr[i] 不能单独删除，将 i 指针右移即可；
- 否则 arr[i] 需要删除。

同样，从右到左遍历数组，若出现 arr[i] > arr[i+1] , 则一定需要删除 arr[i+1]，同理还需进一步判断。

最终，剩下的数组就是非递减的，返回数组长度即可。

参考代码如下：