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

题目链接

Leetcode.1574 删除最短的子数组使剩余数组有序 Rating ： 1932

题目描述

给你一个整数数组 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$

解法：双指针

可以将原数组 arr看成三段。这三段中的任何一段都可能为空。

先用一个指针 j，将其移动到 第二段非递减区间的起始位置。

再用一个指针 i，初始指向 第一段非递减区间的起始位置。

移动指针 i（最多移动到 第一段非递减区间的结束位置），对于 arr[i]，指针 j也要向后移动（若一开始 arr[i] <= arr[j]则不用），使 arr[i] <= arr[j]。

这样 (i , j)中间这一段就是我们需要删除的子数组，长度为 j - i - 1。我们每一次用一个答案 ans更新最小的子数组长度即可。

时间复杂度： $O(n)$

C++代码：

class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr) {
        int n = arr.size();
        int j = n - 1;
        while(j - 1 >= 0 && arr[j] >= arr[j-1]) j--;

        int ans = j;
        if(ans == 0) return ans;

        for(int i = 0;i == 0 || arr[i-1] <= arr[i];i++){
            while(j < n && arr[i] > arr[j]) j++;
            ans = min(ans, j - i - 1);
        }

        return ans;
    }
};

Python代码：

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        j = n - 1
        while j - 1 >= 0 and arr[j] >= arr[j - 1]:
            j -= 1
        ans = j
        if ans == 0:
            return ans

        i = 0
        while i == 0 or arr[i-1] <= arr[i]:
            while j < n and arr[i] > arr[j]:
                j += 1
            ans = min(ans,j-i-1)
            i += 1

        return ans