https://zhuanlan.zhihu.com/p/93486020
给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。
示例 1:
输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
这个问题困扰了一段时间,主要是数组的情况挺多的,总是有考虑不到的情况。后面找到一种算是巧妙的办法,也正好适用与这个题。
思路是在当前元素大于下一个元素的情况下,根据判断前一个和后一个元素的大小,如果前一个小于等于后一个,那么当前元素的值赋值为下一个元素,否则下一个元素的值赋值为当前元素的值。这样的情况下,如果出现两个位置都是递减的情况,那么肯定不满足。也就是根据下面代码中count来判断此种情况。
class Solution {
public boolean checkPossibility(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length - 1; ++i) {
if (nums[i] > nums[i + 1]) {
if (++count == 2)
return false;
if (i == 0 || nums[i - 1] <= nums[i + 1])
nums[i] = nums[i + 1];
else
nums[i + 1] = nums[i];
}
}
return true;
}
}
标签:count,数列,nums,int,递增,元素,递减
From: https://www.cnblogs.com/Szang/p/16984479.html