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

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

题目描述：

给一个数组arr，长度为 $ n $ ，删除一个子数组可以为空，使得剩余的元素是非递减的。返回删除的最短子数组的长度。

数据范围：
$ 1\le n \le 10^5 $

题解：

观察数据范围可知，使用 $ O(n) $ 或者 $ O(n\log n) $ 的做法。由于出现了最大值最小，想到了二分check。可以先求出左侧递增的最大端点 $ l $ ，右侧最小的端点 $ r $ 。满足 $ [0,l],[r,n-1] $ 都是递增的。然后枚举 $ i\in [0,l] $ , $ arr[i] \le a[i + mid + 1] \land i + mid + 1 \ge r $

可以发现重复了很多。考虑双指针优化。左指针 $ [0,l] $ ，右指针 $ [r,n-1] $ 。对于左指针，先移到右指针到 $ arr[r] \ge arr[l] $ 更新答案，然后继续。类似滑动窗口，不过该题是以左窗口为依据，内循环移动右窗口。之前遇到的类似的都是外循环移动右窗口，如果满足了条件内循环移动左窗口。

先用 for循环移动一个窗口，然后在内部，如果满足条件或者不满足条件一直移动另一个窗口，更新答案。

代码：

class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    int findLengthOfShortestSubarray(vector<int> &arr)
    {
        int n = arr.size();
        int l = 0, r = n - 1;
        while (l + 1 < n && arr[l + 1] >= arr[l])
            l++;
        while (r - 1 >= 0 && arr[r - 1] <= arr[r])
            r--;
        if (r <= l)
            return 0;
        int ans = n;
        ans = min(r, n - l - 1);
        if (arr[r] >= arr[l])
        {
            ans = min(ans, r - l - 1);
        }
        for (int i = 0; i <= l; ++i)
        {
            while(r < n && arr[r] < arr[i])
                r++;
            if (r != n)
                ans = min(ans, r - i - 1);
            else break;
        }
        return ans;
    }
};