判断数组能否变成非递减数列 给定一个长度为 n 的整数数组 nums,判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。 示例 1: 输入:[4, 2, 3] 输出:true java题解
时间: 2024-10-16 21:08:24 浏览: 16
要判断一个整数数组能否通过更改一个元素变为非递减数列,你可以考虑以下方法:
1. 首先,遍历整个数组,找出数组的最大值 max_val 和最小值 min_val。这一步可以告诉你需要将哪个元素提升到最大值或者降低到最小值才能保证非递减。
2. 接下来,检查数组中的第二大值(max_val - 1)是否大于等于最小值(min_val)。如果第二大的元素足够大,那么只需要找到并修改比它小的那个元素即可。
3. 如果第二大值小于最小值,你需要确定是否能找到一个元素使其刚好等于最大值。遍历数组,查找第一个大于等于最大值 - 1的元素,如果找不到这样的元素,说明无法仅通过一次更改实现非递减序列。
以下是简单的Java代码示例:
```java
public boolean canMakeNonDecreasing(int[] nums) {
int maxVal = Arrays.stream(nums).max().getAsInt();
int minVal = Arrays.stream(nums).min().getAsInt();
// 如果所有元素已经是非递减的,直接返回真
if (nums[0] <= maxVal) {
return true;
}
// 找到第一个小于 maxVal - 1的元素,尝试提升
int toFix = -1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < maxVal - 1) {
toFix = i;
break;
}
}
// 如果找到了,检查能否通过这个位置提升到最大值
if (toFix != -1 && nums[toFix] <= minVal) {
nums[toFix] = maxVal;
Arrays.sort(Arrays.copyOfRange(nums, 0, toFix + 1));
if (Arrays.equals(Arrays.copyOfRange(nums, toFix + 1, nums.length), Arrays.copyOfRange(nums, 0, toFix + 1))) {
return true;
}
}
return false;
}
```
阅读全文