刷题之旅从数组类型的题目开始。第三十道题目是非递减数列,对应leetcode的题号为665。

image

题目描述

给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的: 对于数组中所有的 i (1 <= i < n),满足 array[i] <= array[i + 1]。

示例 1:

1
2
3
输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

示例 2:

1
2
3
输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

说明:  n 的范围为 [1, 10,000]。

解题思路

只调整一次元素就成为非递减序列?我们考虑简单情况,比如示例的[4,2,3],此时我们知道只需要调整4即可,比如[2,2,3]即可满足非递减序列要求,那么这个序列是符合条件的。但是[4,2,1]就不行,按照刚才的做法,第一步是[2,2,1],但是此时第二个元素还是大于第三个元素,因此还要调整一次才符合,那么这个序列就不符合条件。

显然,这里的关键点是判断前一个元素是否大于后一个元素。一旦有此时就需要进行调整了。

不过如何调整呢?这里就稍微要注意点了,分为两种情况。以[i-1,i.i+1]为例,此时i处元素大于i+1处元素的:

  • 当i-1大于i+1元素的时候,比如[3,4,1]这里的策略是将1调整为4(这是比较简单的调整策略,调整为5的话可能会加重后续的调整),调整之后变成[3,4,4]即可满足
  • 当i-1小于i+1元素的时候,比如[1,4,3]这里策略是将4调小为3,变成[1,3,3]即可满足条件

具体见代码。

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public boolean checkPossibility(int[] nums) {
if(nums.length < 3){
return true;
}
int count = 0;
// 如果第一个元素大于第二个元素,那么为了保证非递减的特性,向下调整第一个元素不大于第二个元素即可
// 比如4 2 3 那么第一步就应该调整4为2即 2 2 3(不要纠结调整为1等其他数字,这里调整的时候策略是相等,因为相等就满足非递减了)
if(nums[0] > nums[1]){
nums[0] = nums[1];
count++;
}
for(int i=1;i+1<nums.length;i++){
int left = nums[i-1];
int right = nums[i+1];
// 如果当前元素大于后面一个元素,那么需要分两种情况讨论
// 比如1 4 3这种情况,为了保证非递减,只能调小第二个元素4,至少减为3才满足条件
// 比如3 4 1这种情况,为了保证非递减,只能调大第三个元素3,至少增为4才满足条件
if(nums[i] > right){
// 先count++,判断count是否大于1了,大于1说明不止一处需要调整,直接返回false
count++;
if(count > 1){
return false;
}
// 对应3 4 1这种情况
if(left > right){
nums[i+1] = nums[i];
}else{
// 对应1 4 3这种情况
nums[i] = right;
}
}
}
return true;
}
}