1574. 删除最短的子数组使剩余数组有序 给你一个整数数组 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]。

提示：

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

Solutions

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int l = 0, r = arr.length-1, R = arr.length-1, min = arr.length-1;
        while(l < arr.length-1 && arr[l] <= arr[l+1]) l++;
        while(r > 0 && arr[r] >= arr[r-1]) r--;
        if(l >= r) return 0;
        if(arr[l] <= arr[r]) return r - l - 1;
        for(int i=l; i>=0 && R >= r; i--){
            while(R >= r && arr[R] >= arr[i]) R--;
            min = Math.min(min,R - i);
        }
        return Math.min(min,r);
    }
}

Ideas

• 方法一：双指针 + 二分查找

  我们先找出数组的最长非递减前缀和最长非递减后缀，分别记为 nums[0..i] 和 nums[j..n−1]。

  如果 i≥j，说明数组本身就是非递减的，返回 0。

  否则，我们可以选择删除右侧后缀，也可以选择删除左侧前缀，因此初始时答案为 min(n−i−1,j)。

  接下来，我们枚举左侧前缀的最右端点 l，对于每个 l，我们可以通过二分查找，在 nums[j..n−1] 中找到第一个大于等于 nums[l] 的位置，记为 r，此时我们可以删除 nums[l+1..r−1]，并且更新答案 ans=min(ans,r−l−1)。继续枚举 l，最终得到答案。

  class Solution {
      public int findLengthOfShortestSubarray(int[] arr) {
          int n = arr.length;
          int i = 0, j = n - 1;
          while (i + 1 < n && arr[i] <= arr[i + 1]) {
              ++i;
          }
          while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
              --j;
          }
          if (i >= j) {
              return 0;
          }
          int ans = Math.min(n - i - 1, j);
          for (int l = 0; l <= i; ++l) {
              int r = search(arr, arr[l], j);
              ans = Math.min(ans, r - l - 1);
          }
          return ans;
      }
    
      private int search(int[] arr, int x, int left) {
          int right = arr.length;
          while (left < right) {
              int mid = (left + right) >> 1;
              if (arr[mid] >= x) {
                  right = mid;
              } else {
                  left = mid + 1;
              }
          }
          return left;
      }
  }
  

• 方法二：双指针

  与方法一类似，我们先找出数组的最长非递减前缀和最长非递减后缀，分别记为 nums[0..i] 和 nums[j..n−1]。

  如果 i≥j，说明数组本身就是非递减的，返回 0。

  否则，我们可以选择删除右侧后缀，也可以选择删除左侧前缀，因此初始时答案为 min(n−i−1,j)。

  接下来，我们枚举左侧前缀的最右端点 l，对于每个 l，我们直接利用双指针找到第一个大于等于 nums[l] 的位置，记为 r，此时我们可以删除 nums[l+1..r−1]，并且更新答案 ans=min(ans,r−l−1)。继续枚举 l，最终得到答案。

  class Solution {
      public int findLengthOfShortestSubarray(int[] arr) {
          int n = arr.length;
          int i = 0, j = n - 1;
          while (i + 1 < n && arr[i] <= arr[i + 1]) {
              ++i;
          }
          while (j - 1 >= 0 && arr[j - 1] <= arr[j]) {
              --j;
          }
          if (i >= j) {
              return 0;
          }
          int ans = Math.min(n - i - 1, j);
          for (int l = 0, r = j; l <= i; ++l) {
              while (r < n && arr[r] < arr[l]) {
                  ++r;
              }
              ans = Math.min(ans, r - l - 1);
          }
          return ans;
      }
  }