给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。
示例 1:
输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
示例 2:
输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
说明: n 的范围为 [1, 10,000]。
思路:
思考什么样的情况下改变一个数据能让一个数组为非递减数队列
第一种情况:乱序元素前后都是有序的,只有它一个乱序
第二种情况:乱序元素在队列的开头或结尾,其他数据也是有序的
代码:
class Solution {
public boolean checkPossibility(int[] nums) {
int i = 0,j = nums.length - 1;
while(i < j && nums[i] <= nums[i + 1])
i++;
while(i < j && nums[j] >= nums[j - 1])
j--;
System.out.println(i + "----" + j); //找出乱序元素的位置
int head = 0;
if(i == 0)
head = Integer.MIN_VALUE;//为零则乱序元素在开头位置
else
head = nums[i - 1];
int next = (j==nums.length - 1)?Integer.MAX_VALUE:nums[j + 1];//最大为结尾位置
if(j - i <= 1 && (head <= nums[j] || nums[i] <= next))//判断乱序元素是否只为一个,并是否有序
return true;
else
return false;
}
}
网友评论