如何使用Java实现非递减数组?
题目描述给出包含n个整数的数组,你的任务是检查它是否可以通过修改至多一个元素变成非下降的。一个非下降的数组array对于所有的i(1
题目描述
给出包含n个整数的数组,你的任务是检查它是否可以通过修改至多一个元素变成非下降的。一个非下降的数组array对于所有的i(1<=i 样例1: ⅰ 输入: [4,2,3] ⅱ 输出: True ⅲ 说明: 可以把第一个数4修改为1,得到[1,2,3]为非下降的数组 样例2: ⅰ 输入: [4,2,1] ⅱ 输出: False ⅲ 说明: 无法通过修改至多一个元素使数组变为非下降的。 解题思路分析
a. 简单的思考可以得到,情况无非为三种:不需要修改就满足条件的、修改一个元素可满足条件的和修改一个元素也无法满足条件的。对于第一种情况,只需遍历数组看是否满足数组的每一项都大于等于前一项,满足则返回true。对于第二种情况,可以枚举要修改的那个数array[i],再去检查array[i]之前的数是否是非下降的,array[i]之后的数是否是非下降的,最后还应该检查array[i-1]<=array[i+1]是否成立(如果array[i]位于边界则无需检查),如果成立则可以将array[i]改为array[i-1]和array[i+1]之间的任何数使数组变为非下降数组,这是情况二,返回true,如果对于所有的i都不成立,则为情况三,返回false。这样做的时间复杂度为O(n^2),额外空间复杂度为O(1)。
b. 修改一个数以后可以变成非下降的数组满足什么条件呢?显然,这样的数组应当满足只存在一对相邻的数不满足非下降的条件,即只存在唯一的i(1<=i
参考程序
Java版本:











































