删除一个元素使数组严格递增
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
在题解中提到检查去除某个元素后的数组是否严格递增,具体是如何实现这一检查的?
▷🦆
为什么在发现第一个违反递增规则的元素对后,不继续检查后续的元素对?
▷🦆
题解中提到尝试删除nums[i]或nums[i+1],请问如何决定删除哪个元素可能会使剩余数组严格递增?
▷