一、题目粗心
标签: 贪婪
https://leetcode.cn/problems/non-decreasing-array
给你一个长度为 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
二、解题思路
最多只有一次批改某个数字的机会，问是否将数组变为非递加数组。举例
例 1:4， 2，3
例 2:-1，4，2，3
例 3:2，3，3， 2，4
当前面的数字小于后面的数字后，例如例 1 中的 2 小于 4，这时能够将批改后面的数字将 4 批改为 2 或批改前面的数字将 2 改为 4。咱们须要找到这个法则，判断批改哪个数字其实跟再后面的一个数大小有关系：
如果再后面的数不存在，例 1 中，4 后面没有数字了咱们间接批改后面的数字为以后数字 2 即可；
如果再后面的数字存在，并且小于以后数字时，例 2 中，咱们须要批改后面的数字 4 为以后数字 2；
如果再后面的数字存在，且大于以后数，例 3 中，咱们须要批改以后数字 2 为后面的数 3。
因为只有一次批改的机会，所以用一个变量 cnt，初始化为 1，批改数字后 cnt 自减 1，当下次再须要批改时，如果 cnt 为 0，间接返回 false。遍历完结后返回 true。
三、解题办法
3.1 Java 实现
public class Solution {public boolean checkPossibility(int[] nums) {
int cnt = 1;
for (int i = 1; i < nums.length; i++) {if (nums[i] < nums[i - 1]) {if (cnt == 0) {return false;}
cnt--;
if (i == 1) {nums[i - 1] = nums[i];
} else if (nums[i] >= nums[i - 2]) {nums[i - 1] = nums[i];
} else {nums[i] = nums[i - 1];
}
}
}
return true;
}
}四、总结小记
- 2022/7/31 今天天气很闷热呀