题目:
给你一个长度为 n
的整数数组 nums
,请你判断在 最多 改变 1
个元素的情况下,该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的: 对于数组中任意的 i
(0 <= i <= n-2)
,总满足 nums[i] <= nums[i + 1]
。
示例 1:
输入: nums = [4,2,3] 输出: true 解释: 你可以通过把第一个 4 变成 1 来使得它成为一个非递减数列。
示例 2:
输入: nums = [4,2,1] 输出: false 解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
提示:
n == nums.length
1 <= n <= 104
-105 <= nums[i] <= 105
题解:
在做这道题的时候,其实就是要找会不会有两次或者多次出现不是非递减数列的情况。这样我们可以通过遍历数组,并且维护一个记录修改次数的变量即可。在每次修改中,如果当前元素大于前两个元素,将当前有问题的元素修改为它的前一个元素即可。
本题代码如下,时间复杂度On。
bool checkPossibility(int* nums, int numsSize) {
if (numsSize <= 1) return true; // 处理特殊情况
bool modified = false; // 记录是否已经进行过一次修改
for(int i = 1; i < numsSize; i++) {
if (nums[i-1] > nums[i]) {
if (modified) return false; // 如果已经修改过一次,则返回 false
if (i >= 2 && nums[i] < nums[i-2]) {
nums[i] = nums[i-1]; // 修改当前元素为前一个元素的值
}
modified = true; // 标记已经修改过一次
}
}
return true;
}
这是我个人的刷题记录,欢迎大家给我的博客提建议,以及如果您有好的leetcode刷题流程,希望能给我指点。
个人的github主页:gushouchuanzhi1 (Deyu Tan) · GitHub
个人的刷题记录仓库:https://github.com/gushouchuanzhi1/2023_personal_training