【每日一题Day157】LC1574删除最短的子数组使剩余数组有序 | 双指针 + 二分查找

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int l = 0;
        while (l < n - 1 && arr[l] <= arr[l + 1]){
            l++;
        }
        if (l == n - 1) return 0;// 该数组就是非递减的 无需删除
        int r = n - 1;
        while (r > l && arr[r] >= arr[r - 1]){
            r--;
        }
        int res = Math.min(n - l, r);
        for (int i = 0; i <= l; i++){
            int index = binarySearch(arr, arr[i], r, n - 1);
            res = Math.min(res, index - i - 1);
        }
        return res;
    }
    public int binarySearch(int[] arr, int target, int l, int r){
        while (l <= r){
            int mid = (l + r) >> 1;
            if (arr[mid] < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return l;
    }
}

class Solution:
    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:
        n = len(arr)
        right = n - 1
        while right and arr[right - 1] <= arr[right]:
            right -= 1
        if right == 0:  # arr 已经是非递减数组
            return 0
        # 此时 arr[right-1] > arr[right]
        ans = right  # 删除 arr[:right]
        left = 0
        while True:  # 枚举 right
            while right == n or arr[left] <= arr[right]:
                ans = min(ans, right - left - 1)  # 删除 arr[left+1:right]
                if arr[left] > arr[left + 1]:
                    return ans
                left += 1
            right += 1
作者：灵茶山艾府
链接：https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/solutions/2189149/dong-hua-yi-xie-jiu-cuo-liang-chong-xie-iijwz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。