What is the best approach to solve Remove One Element to Make the Array Strictly Increasing?

Use a single pass to find the first violation, then test removing either the violating element or the previous one to see if the array becomes strictly increasing.

Can I remove more than one element in this problem?

No, the problem specifically allows removing exactly one element to achieve a strictly increasing array.

How do I handle arrays that are already strictly increasing?

If the array is already strictly increasing, return true immediately without testing any removal.

What should I do if the array has duplicate consecutive elements?

Duplicate consecutive elements violate strict increase, so removing one of the duplicates may fix the array if only one removal is needed.

What is the time complexity for this array-driven solution strategy?

The solution uses at most two linear scans over the array, resulting in O(n) time complexity and O(1) extra space if done in-place.

#1909

Easy

auto_awesome数组·driven

LeetCode 题解工作台

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

给你一个下标从 0 开始的整数数组 nums ，如果恰好删除一个元素后，数组严格递增，那么请你返回 true ，否则返回 false 。如果数组本身已经是严格递增的，请你也返回 true 。数组 nums 是严格递增的定义为：对于任意下标的 1 都满足 nums[i - 1] 。 …

数组

题目描述

给你一个下标从 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

lightbulb

解题思路

方法一：遍历

我们可以遍历数组，找到第一个不满足 $\textit{nums}[i] < \textit{nums}[i+1]$ 的位置 $i$ ，然后检查删除 $i$ 或者 $i+1$ 后的数组是否严格递增，如果是则返回 $\textit{true}$ ，否则返回 $\textit{false}$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        def check(k: int) -> bool:
            pre = -inf
            for i, x in enumerate(nums):
                if i == k:
                    continue
                if pre >= x:
                    return False
                pre = x
            return True

        i = 0
        while i + 1 < len(nums) and nums[i] < nums[i + 1]:
            i += 1
        return check(i) or check(i + 1)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect you to identify the minimal disruption causing non-increasing order.
question_mark
Look for handling edge cases like consecutive equal elements or arrays of length 2.
question_mark
Watch for correct identification of which element to remove when multiple violations exist.

warning

常见陷阱

外企场景

error
Removing the wrong element at a violation can lead to false negatives.
error
Assuming multiple removals are allowed when only one is permitted.
error
Failing to handle arrays that are already strictly increasing.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if removing up to k elements can make the array strictly increasing.
arrow_right_alt
Return the index of the element whose removal fixes the sequence, if possible.
arrow_right_alt
Determine if adding an element can make the array strictly increasing instead of removing.

help

常见问题

外企场景

继续练习

#1911 最大交替子序列和 #1906 查询差绝对值的最小值 #1912 设计电影租借系统