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

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

方法一：寻找非递增相邻下标对

思路与算法

数组 nums 严格递增的充分必要条件是对于任意两个相邻下标对 (i - 1, i) 均有 nums}[i] > \textit{nums}[i-1]。换言之，如果存在下标 i 有 nums}[i] \le \textit{nums}[i-1]，那么 nums 并非严格递增。

因此，我们可以从左至右遍历寻找非递增的相邻下标对。假设对于某个下标对 (i - 1, i) 有 nums}[i] \le \textit{nums}[i-1]，如果我们想使得 nums 在删除一个元素后严格递增，那么必须至少删除下标对 (i - 1, i) 对应的元素之一。

我们可以用 check}(\textit{idx}) 函数来检查数组 nums 删去下标为 idx 的元素后是否严格递增。具体地，我们对 nums 进行一次遍历，在遍历的过程中记录上一个元素的下标，并与当前遍历到的元素进行比较。需要注意的是，下标为 idx 的元素需要被跳过。

代码

[sol1-C++]class Solution {
public:
    bool canBeIncreasing(vector<int>& nums) {
        int n = nums.size();
        // 检查数组 nums 在删去下标为 idx 的元素后是否严格递增
        auto check = [&](const int idx) -> bool{
            for (int i = 1; i < n - 1; ++i){
                int prev = i - 1;
                if (prev >= idx){
                    ++prev;
                }
                int curr = i;
                if (curr >= idx){
                    ++curr;
                }
                if (nums[curr] <= nums[prev]){
                    return false;
                }
            }
            return true;
        };

        for (int i = 1; i < n; ++i){
            // 寻找非递增相邻下标对
            if (nums[i] <= nums[i-1]){
                return check(i - 1) || check(i);
            }
        }
        return true;
    }
};

[sol1-Python3]class Solution:
    def canBeIncreasing(self, nums: List[int]) -> bool:
        n = len(nums)
        # 检查数组 nums 在删去下标为 idx 的元素后是否严格递增
        def check(idx: int) -> bool:
            for i in range(1, n - 1):
                prev, curr = i - 1, i
                if prev >= idx:
                    prev += 1
                if curr >= idx:
                    curr += 1
                if nums[curr] <= nums[prev]:
                    return False
            return True
        
        for i in range(1, n):
            # 寻找非递增相邻下标对
            if nums[i] <= nums[i-1]:
                return check(i) or check(i - 1)
        return True

复杂度分析

时间复杂度：O(n)，其中 n 为 nums 的长度。遍历数组寻找非递增下标对的最坏时间复杂度为 O(n)，执行一次 check}(\textit{idx}) 函数的时间复杂度为 O(n)，而我们至多会执行两次 check}(\textit{idx}) 函数。
空间复杂度：O(1)。