1909. 删除一个元素使数组严格递增

🟢   🔖  数组  🔗 力扣 LeetCode

题目

Given a 0-indexed integer array nums, return true _if it can be made strictly increasing after removing exactly one element, or _false otherwise. If the array is already strictly increasing, returntrue.

The array nums is strictly increasing if nums[i - 1] < nums[i] for each index (1 <= i < nums.length).

Example 1:

Input: nums = [1,2,10 ,5,7]

Output: true

Explanation: By removing 10 at index 2 from nums, it becomes [1,2,5,7].

[1,2,5,7] is strictly increasing, so return true.

Example 2:

Input: nums = [2,3,1,2]

Output: false

Explanation:

[3,1,2] is the result of removing the element at index 0.

[2,1,2] is the result of removing the element at index 1.

[2,3,2] is the result of removing the element at index 2.

[2,3,1] is the result of removing the element at index 3.

No resulting array is strictly increasing, so return false.

Example 3:

Input: nums = [1,1,1]

Output: false

Explanation: The result of removing any element is [1,1].

[1,1] is not strictly increasing, so return false.

Constraints:

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

题目大意

给你一个下标从 0 开始的整数数组 nums ，如果 恰好 删除 一个 元素后，数组 严格递增 ，那么请你返回 true ，否则返回 false 。如果数组本身已经是严格递增的，请你也返回 true 。

数组 nums 是 严格递增 的定义为：对于任意下标的 1 <= i < nums.length 都满足 nums[i - 1] < nums[i] 。

示例 1：

输入： nums = [1,2,10 ,5,7]

输出： true

解释： 从 nums 中删除下标 2 处的 10 ，得到 [1,2,5,7] 。

[1,2,5,7] 是严格递增的，所以返回 true 。

示例 2：

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

输出： false

解释：

[3,1,2] 是删除下标 0 处元素后得到的结果。

[2,1,2] 是删除下标 1 处元素后得到的结果。

[2,3,2] 是删除下标 2 处元素后得到的结果。

[2,3,1] 是删除下标 3 处元素后得到的结果。

没有任何结果数组是严格递增的，所以返回 false 。

示例 3：

输入： nums = [1,1,1]

输出： false

解释： 删除任意元素后的结果都是 [1,1] 。

[1,1] 不是严格递增的，所以返回 false 。

示例 4：

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

输出： true

解释：[1,2,3] 已经是严格递增的，所以返回 true 。

提示：

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

解题思路

1. 定义变量：

   • top：记录当前最大的元素，初始化为 0。
   • secondTop：记录倒数第二大的元素，初始化为 0。
   • deleteCount：记录需要删除的元素个数。

2. 遍历数组：

   • 如果当前元素大于 top，说明当前元素可以加入递增序列：
     • 将 secondTop 更新为 top。
     • 将 top 更新为当前元素。
   • 如果当前元素小于或等于 top，说明当前元素破坏了递增性：
     • 检查当前元素是否大于 secondTop：
       • 是：将 top 更新为当前元素（删除之前的 top 元素）。
       • 否：说明需要删除当前元素。
     • 增加 deleteCount，并检查是否已经超过 1：
       • 如果超过 1，返回 false（不能通过删除一个元素满足条件）。

3. 返回结果：

   • 如果遍历完成后 deleteCount 小于等于 1，返回 true，否则返回 false。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度，单次遍历数组。
• 空间复杂度：O(1)，只使用了常数变量。

代码

var canBeIncreasing = function (nums) {
	let top = 0,
		secondTop = 0,
		deleteCount = 0;
	for (let num of nums) {
		if (num > top) {
			secondTop = top; // 更新倒数第二大的元素
			top = num; // 更新当前最大的元素
		} else {
			if (num > secondTop) {
				// 判断是否可以通过删除前面的元素解决问题
				top = num;
			}
			deleteCount++; // 增加需要删除的元素计数
			if (deleteCount > 1) return false; // 如果删除的元素超过一个，返回 false
		}
	}
	return true; // 如果只需要删除一个或不需要删除，返回 true
};

相关题目

题号	标题	题解	标签	难度	力扣
2289	使数组按非递减顺序排列		栈 数组 链表 1+	🟠	🀄️ 🔗
3334	数组的最大因子得分			🟠	🀄️ 🔗