Question

1574. Shortest Subarray to be Removed to Make Array Sorted

中文文档

Description

Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.

Return _the length of the shortest subarray to remove_.

A subarray is a contiguous subsequence of the array.

 

Example 1:

Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].

Example 2:

Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].

Example 3:

Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.

 

Constraints:

• 1 <= arr.length <= 105
• 0 <= arr[i] <= 109

Solutions

Solution 1

class Solution:
  def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
    n = len(arr)
    i, j = 0, n - 1
    while i + 1 < n and arr[i] <= arr[i + 1]:
      i += 1
    while j - 1 >= 0 and arr[j - 1] <= arr[j]:
      j -= 1
    if i >= j:
      return 0
    ans = min(n - i - 1, j)
    for l in range(i + 1):
      r = bisect_left(arr, arr[l], lo=j)
      ans = min(ans, r - l - 1)
    return ans

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;
  }
}

class Solution {
public:
  int findLengthOfShortestSubarray(vector<int>& arr) {
    int n = arr.size();
    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 = min(n - 1 - i, j);
    for (int l = 0; l <= i; ++l) {
      int r = lower_bound(arr.begin() + j, arr.end(), arr[l]) - arr.begin();
      ans = min(ans, r - l - 1);
    }
    return ans;
  }
};

func findLengthOfShortestSubarray(arr []int) int {
  n := len(arr)
  i, j := 0, n-1
  for i+1 < n && arr[i] <= arr[i+1] {
    i++
  }
  for j-1 >= 0 && arr[j-1] <= arr[j] {
    j--
  }
  if i >= j {
    return 0
  }
  ans := min(n-i-1, j)
  for l := 0; l <= i; l++ {
    r := j + sort.SearchInts(arr[j:], arr[l])
    ans = min(ans, r-l-1)
  }
  return ans
}

Solution 2

class Solution:
  def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
    n = len(arr)
    i, j = 0, n - 1
    while i + 1 < n and arr[i] <= arr[i + 1]:
      i += 1
    while j - 1 >= 0 and arr[j - 1] <= arr[j]:
      j -= 1
    if i >= j:
      return 0
    ans = min(n - i - 1, j)
    r = j
    for l in range(i + 1):
      while r < n and arr[r] < arr[l]:
        r += 1
      ans = min(ans, r - l - 1)
    return ans

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;
  }
}

class Solution {
public:
  int findLengthOfShortestSubarray(vector<int>& arr) {
    int n = arr.size();
    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 = min(n - 1 - i, j);
    for (int l = 0, r = j; l <= i; ++l) {
      while (r < n && arr[r] < arr[l]) {
        ++r;
      }
      ans = min(ans, r - l - 1);
    }
    return ans;
  }
};

func findLengthOfShortestSubarray(arr []int) int {
  n := len(arr)
  i, j := 0, n-1
  for i+1 < n && arr[i] <= arr[i+1] {
    i++
  }
  for j-1 >= 0 && arr[j-1] <= arr[j] {
    j--
  }
  if i >= j {
    return 0
  }
  ans := min(n-i-1, j)
  r := j
  for l := 0; l <= i; l++ {
    for r < n && arr[r] < arr[l] {
      r += 1
    }
    ans = min(ans, r-l-1)
  }
  return ans
}