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

Categories:

题目描述
思路分析
1. 解法一：双指针（推荐）
相似题目

题目描述

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

思路分析

解法一：双指针（推荐）

核心思路：

找到最长非递减前缀与后缀。

先取移除前缀或后缀的最小值。

再用双指针尝试拼接前缀与后缀，更新最小删除长度。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int left = 0;
        while (left + 1 < n && arr[left] <= arr[left + 1]) {
            left++;
        }
        if (left == n - 1) {
            return 0;
        }

        int right = n - 1;
        while (right > 0 && arr[right - 1] <= arr[right]) {
            right--;
        }

        int res = Math.min(n - left - 1, right);

        int i = 0;
        int j = right;
        while (i <= left && j < n) {
            if (arr[i] <= arr[j]) {
                res = Math.min(res, j - i - 1);
                i++;
            } else {
                j++;
            }
        }

        return res;
    }
}

func findLengthOfShortestSubarray(arr []int) int {
	n := len(arr)
	left := 0
	for left+1 < n && arr[left] <= arr[left+1] {
		left++
	}
	if left == n-1 {
		return 0
	}

	right := n - 1
	for right > 0 && arr[right-1] <= arr[right] {
		right--
	}

	res := n - left - 1
	if right < res {
		res = right
	}

	i, j := 0, right
	for i <= left && j < n {
		if arr[i] <= arr[j] {
			if j-i-1 < res {
				res = j - i - 1
			}
			i++
		} else {
			j++
		}
	}

	return res
}

相似题目

题目	难度	考察点
1574. 删除最短的子数组使剩余数组有序	中等	双指针
581. 最短无序连续子数组	中等	双指针
986. 区间列表的交集	中等	双指针
88. 合并两个有序数组	简单	双指针
977. 有序数组的平方	简单	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/18356147