Skip to content

Latest commit

 

History

History
195 lines (139 loc) · 5.97 KB

1574.md

File metadata and controls

195 lines (139 loc) · 5.97 KB
title description keywords
1574. 删除最短的子数组使剩余数组有序
LeetCode 1574. 删除最短的子数组使剩余数组有序题解，Shortest Subarray to be Removed to Make Array Sorted，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
1574. 删除最短的子数组使剩余数组有序
删除最短的子数组使剩余数组有序
Shortest Subarray to be Removed to Make Array Sorted
解题思路
栈
数组
双指针
二分查找
单调栈

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

🟠 Medium  🔖  栈 数组 双指针 二分查找 单调栈  🔗 力扣 LeetCode

题目

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 <= 10^5
  • 0 <= arr[i] <= 10^9

题目大意

给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。

一个子数组指的是原数组中连续的一个子序列。

请你返回满足题目要求的最短子数组的长度。

示例 1：

输入： arr = [1,2,3,10,4,2,3,5]

输出： 3

解释： 我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。

另一个正确的解为删除子数组 [3,10,4] 。

示例 2：

输入： arr = [5,4,3,2,1]

输出： 4

解释： 由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。

示例 3：

输入： arr = [1,2,3]

输出： 0

解释： 数组已经是非递减的了，我们不需要删除任何元素。

示例 4：

输入： arr = [1]

输出： 0

提示：

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

解题思路

  1. 寻找左右有序区间

首先确定从两端扩展的两个有序区间：

  • 左侧有序区间: 从 arr[0] 开始向右找出最长的非递减子数组，标记为 [0, left]。

  • 右侧有序区间: 从 arr[n-1] 开始向左找出最长的非递减子数组，标记为 [right, n-1]。

  • 如果整个数组已经有序 (left == n - 1)，直接返回 0。

  1. 初步计算结果

在只保留左侧或右侧区间的情况下，分别删除的子数组长度为：

  • 删除 [left+1, n-1]，即 n - left - 1。
  • 删除 [0, right-1]，即 right。

初始结果取二者的较小值。

  1. 合并左右区间

尝试合并左侧和右侧的有序区间。用两个指针 i 和 j：

  • i 从左侧有序区间 [0, left] 开始遍历。
  • j 从右侧有序区间 [right, n-1] 开始遍历。

对于每对 arr[i] 和 arr[j]：

  • 如果 arr[i] <= arr[j]，说明 arr[i] 和 arr[j] 可以连通，将删除区间长度更新为 j - i - 1，并向右移动 i。
  • 如果 arr[i] > arr[j]，说明当前的 j 无法与 i 连通，需要向右移动 j。
  1. 返回结果

最终返回最小的删除区间长度 result。

复杂度分析

  • 时间复杂度：O(n)，找到左右有序区间的复杂度为 O(n)，双指针合并左右区间的复杂度为 O(n)，总时间复杂度为 O(n)。
  • 空间复杂度：O(1)，只使用了常数级别的额外空间。

代码

/**
 * @param {number[]} arr
 * @return {number}
 */
var findLengthOfShortestSubarray = function (arr) {
	const n = arr.length;
	// 寻找左右有序区间
	let left = 0;
	while (left + 1 < n && arr[left] <= arr[left + 1]) {
		left++;
	}

	if (left == n - 1) return 0;

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

	// 初步计算结果
	let result = Math.min(n - left - 1, right);

	// 合并左右区间
	let i = 0,
		j = right;

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

	return result;
};

相关题目

题号 标题 题解 标签 难度 力扣
2970 统计移除递增子数组的数目 I 数组 双指针 二分查找 1+ 🟢 🀄️ 🔗
2972 统计移除递增子数组的数目 II 数组 双指针 二分查找 🔴 🀄️ 🔗