Easy

题目描述

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

提示：

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

解题思路

这道题有两种主要思路：

方法一：暴力模拟（推荐） 遍历每个位置，尝试删除该位置的元素，然后检查剩余数组是否严格递增。这种方法简单直观，由于数组长度最大为1000，时间复杂度完全可以接受。

方法二：一次遍历优化 通过一次遍历找到所有不满足严格递增的位置，如果这样的位置超过1个，直接返回false。如果只有1个或0个这样的位置，再判断删除相应元素后是否能形成严格递增序列。

对于这道题，由于数据规模较小且要求实现简单，推荐使用方法一。具体实现时，对于每个可能删除的位置i，我们需要检查删除nums[i]后的数组是否严格递增。检查时要注意跳过被删除的位置。

需要特别注意的是，如果数组本身就是严格递增的，应该直接返回true，因为题目允许"如果数组本身就是严格递增的，请你也返回true"。

代码实现

class Solution {
public:
    bool canBeIncreasing(vector<int>& nums) {
        int n = nums.size();
        
        // 尝试删除每个位置的元素
        for (int i = 0; i < n; i++) {
            if (isStrictlyIncreasing(nums, i)) {
                return true;
            }
        }
        
        return false;
    }
    
private:
    bool isStrictlyIncreasing(vector<int>& nums, int skip) {
        int prev = -1;
        for (int i = 0; i < nums.size(); i++) {
            if (i == skip) continue;
            if (prev >= nums[i]) return false;
            prev = nums[i];
        }
        return true;
    }
};

class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        def is_strictly_increasing(skip_index):
            prev = -1
            for i in range(len(nums)):
                if i == skip_index:
                    continue
                if prev >= nums[i]:
                    return False
                prev = nums[i]
            return True
        
        # 尝试删除每个位置的元素
        for i in range(len(nums)):
            if is_strictly_increasing(i):
                return True
        
        return False

public class Solution {
    public bool CanBeIncreasing(int[] nums) {
        int n = nums.Length;
        
        // 尝试删除每个位置的元素
        for (int i = 0; i < n; i++) {
            if (IsStrictlyIncreasing(nums, i)) {
                return true;
            }
        }
        
        return false;
    }
    
    private bool IsStrictlyIncreasing(int[] nums, int skip) {
        int prev = -1;
        for (int i = 0; i < nums.Length; i++) {
            if (i == skip) continue;
            if (prev >= nums[i]) return false;
            prev = nums[i];
        }
        return true;
    }
}

var canBeIncreasing = function(nums) {
    let removed = false;
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] <= nums[i-1]) {
            if (removed) return false;
            removed = true;
            
            if (i >= 2 && nums[i] <= nums[i-2]) {
                nums[i] = nums[i-1];
            }
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)外层循环O(n)次，每次检查数组需要O(n)时间
空间复杂度O(1)只使用常数额外空间

相关题目