leetcode
leetcode 1651 ~ 1700
删除一个元素使数组严格递增

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

难度:

标签:

题目描述

代码结果

运行时间: 20 ms, 内存: 16.6 MB


// Java Stream solution
// 思路:
// 使用Java Stream进行实现。
// 首先,利用Stream遍历数组,检查是否有不满足严格递增的情况,
// 如果有,尝试移除当前元素或者前一个元素,检查剩下的数组是否严格递增。

import java.util.stream.IntStream;

public class SolutionStream {
    public boolean canBeIncreasing(int[] nums) {
        long count = IntStream.range(1, nums.length)
            .filter(i -> nums[i] <= nums[i - 1])
            .count();
        if (count == 0) return true;
        for (int i = 0; i < nums.length; i++) {
            final int idx = i;
            if (IntStream.range(0, nums.length)
                .filter(j -> j != idx)
                .map(j -> nums[j])
                .reduce((a, b) -> a < b ? b : Integer.MAX_VALUE) != Integer.MAX_VALUE) {
                return true;
            }
        }
        return false;
    }
}

解释

方法:

题解采用了一种迭代的方式来确定是否可以通过删除一个元素使数组变成严格递增的。主要步骤包括:1) 遍历数组,寻找违反严格递增规则的相邻元素对(nums[i] >= nums[i+1])。2) 当找到这样的元素对时,尝试删除 nums[i] 或 nums[i+1],并检查剩余部分是否严格递增。3) 如果删除 nums[i+1] 后 nums[i+2:] 是严格递增的,并且 nums[i] < nums[i+2] 或 nums[i] 是数组的第一个元素,则返回true。4) 如果删除 nums[i] 后 nums[i+1:] 是严格递增的,并且 nums[i-1] < nums[i+1] 或 nums[i+1] 是数组的第一个元素,则返回true。5) 如果数组本身是严格递增的,也直接返回true。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在题解中提到检查去除某个元素后的数组是否严格递增,具体是如何实现这一检查的?
题解中实现检查数组是否严格递增的方法是通过一个辅助函数 `isIncreasing(a)`。这个函数使用 Python 的 `zip` 函数和列表推导式来比较数组中的每个元素与其后继元素。具体实现为:`all(b < c for b, c in zip(a, a[1:]))`,这里 `zip(a, a[1:])` 会生成一个包含相邻元素对的迭代器,然后对于每对元素 (b, c),检查 b 是否小于 c。如果所有相邻元素对都满足这一条件,函数返回 `True`,表示数组是严格递增的;否则返回 `False`。
🦆
为什么在发现第一个违反递增规则的元素对后,不继续检查后续的元素对?
题解中的策略是在发现第一个违反递增规则的元素对 `nums[i] >= nums[i+1]` 后,尝试通过删除一个元素来使数组恢复严格递增的状态。这种方法基于的假设是,如果可以通过删除一个元素使数组变为严格递增,则最多只会有一处违反严格递增的情况。如果在尝试删除一个元素之后,数组仍然不能变为严格递增,或者在尝试删除后发现删除的方法不符合条件(如删除后的元素仍然不满足严格递增),则直接返回 `False`。这样做可以避免不必要的后续检查,提高算法效率。
🦆
题解中提到尝试删除nums[i]或nums[i+1],请问如何决定删除哪个元素可能会使剩余数组严格递增?
在决定删除 `nums[i]` 或 `nums[i+1]` 时,题解中采用的策略是尝试两种可能的删除方式,并检查哪种方式可以使得剩余数组严格递增。首先尝试删除 `nums[i+1]`,并检查剩余部分 `nums[i+2:]` 是否严格递增,并确保 `nums[i] < nums[i+2]`(如果 `i+2` 在数组范围内)。如果这种方式失败,即 `nums[i+1]` 删除后数组不严格递增或 `nums[i] >= nums[i+2]`,则尝试删除 `nums[i]`,并检查剩余部分 `nums[i+1:]` 是否严格递增,且 `nums[i-1] < nums[i+1]`(如果 `i-1` 在数组范围内)。这种动态的检查方式允许算法根据具体情况灵活决定删除哪个元素,从而增加成功使数组严格递增的可能性。

相关问题